750
Modeling Arithmetic, Computation, and Languages
S e c t i o n 9 . 3 review
tecHniQueS
• Compute the output string for a given finite-state
machine and a given input string.
• Draw a state graph from a state table and vice versa.
• Construct a finite-state machine to act as a recognizer for a certain type of input.
• Find a regular expression given the description of
a regular set.
• Decide whether a given string belongs to a given
regular set.
• Minimize finite-state machines.
• Construct sequential networks for finite-state
machines.
main iDeaS
• Finite-state machines have a synchronous, deterministic mode of operation and limited memory
capabilities.
• The class of sets that finite-state machines can recognize is the class of all regular sets; hence, their
recognition capabilities are limited.
• Unreachable states can be removed from a machine.
• After unreachable states have been removed from a
machine, a minimized version of that machine can
be found that produces the same output strings for
all input strings.
• Any finite-state machine can be built using a network of AND gates, OR gates, inverters, and delay
elements.
exeRciSeS 9.3
1. For each input sequence and machine given, compute the corresponding output sequence (starting state is
always s 0 ).
a. 011011010
b. abccaab
W
present state
next state
output
present input
a
b
c
s 0
s 2
s 0
s 3
a
s 1
s 0
s 2
s 3
b
s 2
s 2
s 0
s 1
a
s 3
s 1
s 2
s 0
c