Question

Describe a non-deterministic two-tape TM for testing whetehr the string on the first tape is a substring of the string in the second a tape. choose your own test cases

Answer 1

W e will now build a machine to demonstrate two properties at once: a multi tape machine that uses nondeterminism. We will develop a machine with two tapes, T1 and T2, with both tapes having input alphabet of   and tape alphabet. The machine accepts if the (a+b)* string in T2, and rejects otherwise.

Start JFLAP if it is not already running; if it is running select the menu item File: New. From the list presented choose a new Multi tape Turning machine. Before the editor appears, a dialog asks for the number of tapes for this new TM. The default is 2; we want two tapes, but nevertheless click on 2 and see them popup menu with integer 2 through 5, allowing the choice of the number of tapes for this machine, select 2 once more and click on OK. A new window with the familiar automation editor appears. Create the three states q0, q1, q2. Make q0 the initial state and q2 the single final state. Create a single transition from q0 to q2. Instead of a single row as seen earlier for single-tape machine transitions, for an n tape machine, there are n rows as there are n tape heads to read a symbol from, write and move. The ith row directs what must be read from, written to, and how the head of an ith tape.

In the first row, enter as the symbol to be read and written and set the direction symbol to S; recall that to enter you leave a field empty. In the second row, enter b as the symbol to be read and written and set the direction symbol to be R, Finish editing the transition, your transition will appear with the label; S|b;b; R. The n independent controls of each of the n read-write heads are delimited by the vertical bars |. The transitions from q0 to q2 handle the special case where T1 is empty, in which case T1 is always a substring of T2.