Describe, at a high level, a nondeterministic, two-tape Turing machine that take
ID: 3850113 • Letter: D
Question
Describe, at a high level, a nondeterministic, two-tape Turing machine that takes an input of the form x#w_1#w_2#w_3#. #w_n (where n greaterthanorequalto 3 and where x and all strings w_i are strings in {a, b, c}^+) and accepts the input if and only if there exist distinct integers p, q and r in the range {1, 2, 3, ., n} such that w_p w_q w_r = x. For example, the input abbacab#ab#bbbc#abb#cca#ac should be accepted because the strings w_3 = abb, w_5 = ac and w_1 = ab can be concatenated to form x = abbacab. However, the input cccabc#aa#ab#ac#ba#bb should not be accepted as there is no way to concatenate 3 strings from w_1, ., w_n to form the string x = cccabc.Explanation / Answer
--> To design nondeterministic turing machine for given language, consider following high level description :
- Copy string x into second tape and delete from first tape.
we have w1#w2#w3...#wn on first tape and x on second tape.
- start comparing prefix of x with string : w1, w2,...wn.
step a :if there is at least one prefix of x that matches with any of the string w1,w2..wn then divide x into following manner :
x = x1#x2. where x1 is a prefix that matched and x2 is remaining string.
if there are more than 1 string matched with prefix of x then :
add nondeterminism here and consider each of the matched strings and divide it further as given in step - a.
step b :if no strings are matched with prefix then reject the given string.
- keep repeating step 2 for x2 until x2 becomes empty.
- if matching string found, accept.
if you have any doubts then you can ask in comment section.