Automata

Turing machine for anbncn | n ≥ 1

Previously we have seen example of turing machine for anbn | n ≥ 1
We will use the same concept for anbncn | n ≥ 1 also.

Approach for anbncn | n ≥ 1

  1. Mark 'a' then move right.
  2. Mark 'b' then move right
  3. Mark 'c' then move left
  4. Come to far left till we get 'X'
  5. Repeat above steps till all 'a', 'b' and 'c' are marked
  6. At last if everything is marked that means string is accepted.

TAPE movement for string "aaabbbccc":


Explanation of TAPE movement

    Step 1-2
  1. Input is given as "aaabbbccc" (scan string from left to right)
  2. Mark 'a' as 'X' and move one step right
  3. Reach unmarked 'b' and pass every 'a' and 'Y'(in case) on the way to 'b'
  4. Step 3-4
  5. Mark 'b' as 'Y' and move one step right
  6. Reach unmarked 'c' and pass every 'b' and 'Z'(in case) on the way to 'c'
  7. Mark 'c' as 'Z' and move one step left cause now we have to repeat process
  8. Reach unmarked 'X' and pass every 'Z', 'b', 'Y', 'a' on the way to 'X'
  9. Move to 'a' and repeat the process
  10. Step 5-9
  11. Step 1-4 are repeated
  12. Step 10
  13. When TAPE header reaches 'X' and next symbol is 'Y' that means 'a's are finished
  14. Check for 'b's and 'c's by going till BLANK(in right) and passing 'Y' and 'Z' on the way
  15. If no 'b' and 'c' are not found that means string is accepted

State Transition Diagram

We have designed state transition diagram for anbncn | n ≥ 1 as follows:
  1. Following Steps:
    a. Mark 'a' with 'X' and move towards unmarked 'b'
    b. Move towards unmarked 'b' by passing all 'a's
    c. To move towards unmarked 'b' also pass all 'Y's if exist

  2. Following Steps:
    a. Mark 'b' with 'Y' and move towards unmarked 'c'
    b. Move towards unmarked 'c' by passing all 'b's
    c. To move towards unmarked 'c' also pass all 'Z's if exist

  3. Following Steps:
    a. Mark 'c' with 'Z' and move towards first 'X' (in left)
    b. Move towards first 'X' by passing all 'Z's, 'b's, 'Y's and 'a's
    c. When 'X' is reached just move one step right by doing nothing.

  4. To check all the 'a's, 'b's and 'c's are over add loops for checking 'Y' and 'Z' after "we get 'X' followed by 'Y'"
    To reach final state(qf) just replace BLANK with BLANK and move either direction