T Naughton, NUIM
Back to SE307 home

Lab 6 - Machines simulating machines (finite automata)

Make sure that you have answered problem 5.5 from the previous lab.

A configuration of a machine is the minimum set of information you need to take the next computation step and all subsequent computation steps. For a FA, a configuration consists of (i) the current state, and (ii) the remaining input symbols. In this laboratory session you will construct a TM that is able to compute the next configuration of a FA computation given the current one.

Machine 6.1 Construct a TM that accepts the language of 4-tuples of the form (M, i, q, q'), where M is a FA of the form (Q,S,d,q₀,F), iÎS* is an input string, qÎQ is the current state of the FA, and q'ÎQ is the next state of the FA. To make things simpler, assume that Q is restricted to {00, 01, 10, 99}, that S is restricted to {a, b}, that q₀=00, that F={99}, and that M has already been syntax-checked so we can represent it by a cut-down version containing only a few transitions from transition function d. Each transition in d will have the following form: a *, followed by a state, followed by #, followed by a symbol, followed by #, followed by a state. The VTM seems to have trouble with # and * symbols so when programming, use X instead of # and use Z instead of *.

For example, ___QS*00#a#10q0F_abba_00_10___ would be accepted, ___QS*00#a#10*01#a#10*01#b#99q0F_bb_01_99___ would be accepted, and ___QS*00#a#10*01#b#10*q0F_baab_00_10___ would not be accepted. You can assume that the transition you need will always be given (because the input will have been syntax checked), even though for simplicity not all transitions in d will be specified in the input.

Your TM will signify that it accepts the word by writing a `T' after the 4-tuple it has been passed as input.