[Overview] [Previous] [Next]

Sorting

Given a string consisting of a's and b's, this machine will rearrange the string so that all the a's come before all the b's.

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
-------------------------------------------------------
Find the leftmost 'b'
-------------------------------------------------------
  q1     |    a     |     a     |      R      |   q1
  q1     |    b     |     b     |      R      |   q2
  q1     |    #     |     #     |      L      | final
-------------------------------------------------------
Look for an 'a' to the right of a 'b', replace with 'b'
-------------------------------------------------------
  q2     |    a     |     b     |      L      |   q3
  q2     |    b     |     b     |      R      |   q2
  q2     |    #     |     #     |      L      | final
-------------------------------------------------------
Already replaced 'a' with 'b', now replace 'b' with 'a'
-------------------------------------------------------
  q3     |    b     |     a     |      L      |   q0