Tuesday, December 20, 2011

Section 12.3-Finite-State Machines with Output-Discrete Mathematics and Its Applications

Rosen, Discrete Mathematics and Its Applications, 6th edition
Extra Examples
Section 12.3— Finite-State Machines with Output

p.807, icon at Example 6
#3. Determine the set of bit strings recognized by the following deterministic finite-state automaton.

Solution:
If the bit string ends in 0, you end in state s2. If the bit string ends in 1, you end in state s1. Therefore, this automaton recognizes all bit strings that end in 0.


p.807, icon at Example 6
#4. Determine the set of bit strings recognized by the following deterministic finite-state automaton.

Solution:
If the bit string has two consecutive 0’s or two consecutive 1’s, you end in state s3. If the bit string has no two consecutive 0’s or two consecutive 1’s, you end in either state s1 or s2. Therefore, this automaton recognizes all bit strings that alternate 0’s and 1’s.


p.807, icon at Example 6
#5. Determine the set of bit strings recognized by the following deterministic finite-state automaton.

Solution:
The string must end in 01 in order to be recognized by this automaton. If the string ends in 11, the string ends in state s0. If the string ends in 0, the string ends in state s1.

No comments:

Post a Comment