The Student Room Group

Turing Machine diagram advice

I am studying Theory of Computation and writing a Turing Machine diagram is really giving me headaches!

The exam is soon and I'm struggling to understand how to write a Turing Machine for any given language.

So I know how a Turing Machine works, I know how to trace a Turing machine for a given string. But drawing one out is a totally different kettle of fish!

I don't know when the head should move left or right or when to mark a character or when to loop within a state... Like this



Is there a step by step process for writing these out because every Turing Machine is different, so I can't find any standard way of creating them. Even better, is there a "trick" to creating them easily?

For examples sake let's just use L = {a^i b^i | i > 0}
(edited 8 years ago)
Reply 1
Avatar for asshоle
asshоle
a^i b^i

...does this mean i number of a's and i number of b's?

If so, you need a start state (which does not accept as i must be > 0), from there allow an 'a' to stransition to the next stage. Then allow a 'b' to transition to accept state. The accept stage transitions back to the previous state using an 'a'. That is all.
Original post by asshоle
a^i b^i

...does this mean i number of a's and i number of b's?

If so, you need a start state (which does not accept as i must be > 0), from there allow an 'a' to stransition to the next stage. Then allow a 'b' to transition to accept state. The accept stage transitions back to the previous state using an 'a'. That is all.


No, it means i number of 'a's followed by i number of 'b's. You cannot describe this set with a FSM (which is what it seems you are trying to do). This should be easy to see if you are familiar with the Myhill-Nerode theorem.

OP, I prefer to draw a table with axis for the possible inputs and possible states. It's far more readable imo.
(edited 8 years ago)
Reply 3
Avatar for UWS
UWS
OP
21
Original post by Jooooshy
No, it means i number of 'a's followed by i number of 'b's. You cannot describe this set with a FSM (which is what it seems you are trying to do). This should be easy to see if you are familiar with the Myhill-Nerode theorem.

OP, I prefer to draw a table with axis for the possible inputs and possible states. It's far more readable imo.


I understand but for my exam they want it in diagram format.

I just want a quicker way of determining how many states to have, when to move the head left or right and when to mark/unmark a symbol... That's something I'm trying to get to grips to.

Does drawing a diagram make things easier? but I'd still need to know the number of states...
Reply 4
Avatar for asshоle
asshоle
Original post by Jooooshy
No, it means i number of 'a's followed by i number of 'b's. You cannot describe this set with a FSM (which is what it seems you are trying to do). This should be easy to see if you are familiar with the Myhill-Nerode theorem.

OP, I prefer to draw a table with axis for the possible inputs and possible states. It's far more readable imo.


Ah right - yea I remember now. Turing machine can describe it though as it can count.
Original post by UWS
I understand but for my exam they want it in diagram format.

I just want a quicker way of determining how many states to have, when to move the head left or right and when to mark/unmark a symbol... That's something I'm trying to get to grips to.

Does drawing a diagram make things easier? but I'd still need to know the number of states...


These are all things you should figure out before drawing it.. Again, a table would help but isn't necessary. Take your example. The way I'd approach it (assuming the tape already has both endmarkers) is to zip across the input tape, find the first b, erase it, go and find a corresponding a, erase that, repeat until either you hit a problem or the tape is empty. From this you can figure out what states you need. From then on it's simply deciding what to do at each state for each input.. The transition arrows merely describe the actions you take. For clarity I'll explain the beginnings of a construction: I'd have a state for zipping across all 'a's, moving right and not overwriting the tape each time. Then, once I hit a 'b', I'd go into a different state (for finding a corresponding 'a'); the transition would be to overwrite (or mark, whatever you prefer) the 'b' with the empty symbol and move left. Then I need to do a similar thing to deal with the corresponding 'a' (assuming it's there); this is done with a state the ignores blank symbols, fails on finding anything other than an 'a', and if it finds an 'a' it deletes it and goes back to traversing rightwards in hope of finding either a 'b' or the right endmarker. Hopefully this gives you an idea of how to go from visualising the machine to writing a state/transition diagram to represent it.
Original post by asshоle
Ah right - yea I remember now. Turing machine can describe it though as it can count.


That language is context-free, so you can describe it with a pushdown automaton.
Reply 7
Avatar for asshоle
asshоle
Original post by Jooooshy
That language is context-free, so you can describe it with a pushdown automaton.


yea but the question says turing machine...
Original post by asshоle
yea but the question says turing machine...


I wasn't answering OP's question, merely making a remark :smile:

Quick Reply

Related discussions

Latest

Trending

Trending

Articles for you