[Overview] [Previous] [Next]

Recognizing a Language

This machine will match strings of the form {an timesbn times: n >= 0}.
q1 is the only final state.
current  |  symbol  |  symbol   |             |  next
state    |  read    |  written  |  direction  |  state
------------------------------------------------------
Find the left end of the input
------------------------------------------------------
  q0     |    a     |     a     |      L      |   q0
  q0     |    b     |     b     |      L      |   q0
  q0     |    #     |     #     |      R      |   q1
------------------------------------------------------
Erase the 'a' at the left end of the input
------------------------------------------------------
  q1     |    a     |     #     |      R      |   q2
------------------------------------------------------
Find the right end of the input
------------------------------------------------------
  q2     |    a     |     a     |      R      |   q2
  q2     |    b     |     b     |      R      |   q2
  q2     |    #     |     #     |      L      |   q3
------------------------------------------------------
Erase the 'b' at the left end of the input
------------------------------------------------------
  q3     |    b     |     #     |      L      |   q0


Copyright 1996 by David Matuszek
Last modified Mar 25, 1996