CODEWITHSUNDEEP
grammarautomataturing-machinesautomata-theory
Secret society
Secret society

Reputation: 47

Building Turing machine graph

I have been trying making a Turing machine graph recognizing the language :

{(ab)^n(ba)^n | n >0}

How to build the Turing machine graph for the above-mentioned language?

Upvotes: 0

Views: 150

Answers (2)

trincot
trincot

Reputation: 350821

I would start removing pairs of characters from the outer sides of the input inwards:

  • If the input is empty, accept
  • Assert the leftmost pair is "ab" and remove it.
  • Go to the extreme right.
  • Assert the rightmost pair is "ba" and remove it.

Now you can either walk back to the extreme left and repeat, or you can perform the above procedure in reverse (so that you make use of the reversed traversal to also remove some stuff):

  • If the input is empty, accept
  • Assert the rightmost pair is "ba" and remove it.
  • Go to the extreme left.
  • Assert the leftmost pair is "ab" and remove it.

Then repeat from the top.

Here is a runnable implementation of that idea:

createTuring({
    transitions: [
        { state: "start",   read: "_",              move: "R", nextState: "accept"  },
        { state: "start",   read: "a",  write: "_", move: "R", nextState: "leftb2"  },
        { state: "start",   read: "b",              move: "R", nextState: "reject"  },
        { state: "leftb2",  read: "b",  write: "_", move: "R", nextState: "goright" },
        { state: "leftb2",  read: "a_",             move: "R", nextState: "reject"  },
        { state: "goright", read: "ab",             move: "R", nextState: "goright" },
        { state: "goright", read: "_",              move: "L", nextState: "righta"  },
        { state: "righta",  read: "a",  write: "_", move: "L", nextState: "rightb"  },
        { state: "righta",  read: "b_",             move: "L", nextState: "reject"  },
        { state: "rightb",  read: "b",  write: "_", move: "L", nextState: "righta2" },
        { state: "rightb",  read: "a_",             move: "L", nextState: "reject"  },
        { state: "righta2", read: "_",              move: "L", nextState: "accept"  },
        { state: "righta2", read: "a",  write: "_", move: "L", nextState: "rightb2" },
        { state: "righta2", read: "b",              move: "L", nextState: "reject"  },
        { state: "rightb2", read: "b",  write: "_", move: "L", nextState: "goleft"  },
        { state: "rightb2", read: "a_",             move: "L", nextState: "reject"  },
        { state: "goleft",  read: "ab",             move: "L", nextState: "goleft"  },
        { state: "goleft",  read: "_",              move: "R", nextState: "lefta"   },
        { state: "lefta",   read: "a",  write: "_", move: "R", nextState: "leftb"   },
        { state: "lefta",   read: "b_",             move: "R", nextState: "reject"  },
        { state: "leftb",   read: "b",  write: "_", move: "R", nextState: "start"   },
        { state: "leftb",   read: "a_",             move: "R", nextState: "reject"  },
    ],
    initState: "start",
    tape: "ababababbabababa",
});
<script src="https://trincot.github.io/turing.js"></script>

The above used transition table has explicit transitions to a reject state if the input does not match the pattern. If you are happy with a rejection that consists of just halting in any state that is not an accept state, you can remove those transitions from the table.

Upvotes: 0

Patrick87
Patrick87

Reputation: 28312

  1. find the substring bb by identifying two consecutive instances of b
  2. cross these off by replacing with a tape symbol X
  3. bounce across the section of instances of X, crossing off matching symbols in alternating fashion (first cross off matching instances of a, then b, then a, etc.)
  4. halt-accept if the tape is empty after crossing off matching instances of a
  5. halt-reject if you run out of symbols early or if the tape is empty after crossing out instances of b

I'll leave defining states as an exercise but if you need help with that I can revisit this answer later. As a hint - you will need either one or a couple of states to handle each of the above steps.

Upvotes: 1

Related Questions