CSCE 4115/5400 ASSIGNMENT #7 Due Wednesday, December 3, 2014 1. Design Turing machines to recognize the following languages. You should use as many...

CSCE 4115/5400 ASSIGNMENT #7 Due Wednesday, December 3, 2014 1. Design Turing machines to recognize the following languages. You should use as many tapes as necessary to simplify the design but the Turing machine must be deterministic and must halt for all input. The algorithm employed by the Turing machine should be fully explained and the Turing machine should be tested on some example strings using Prolog. Note that example strings should include both strings in the language and strings not in the language.

(a) L = fw#w R #w jw 2 f 0;1 g g . Example strings in L include 01#10#01, 110#011#110, and 000#000#000.

(b) L = fb n # b m # b n + m j b i is iin binary, i 1g. Example strings in this language include 10#11#101, 111#100#1011, and 101#110#1011.

(c) L = fw jw is a string of the form (0 1) , with all sets of 0's the same length g. The strings of this language are ", 0101, 001001, 00010001, ....

2. For each of the following languages L, indicate whether L is recursive, recursively enumerable but not recursive, or not recursively enumerable. In each case, prove your answer by describing a Turing machine to decide (or compute) the solution to the problem and/or by proving the non-existence of a deciding (or computing) Turing machine.

(a) L = f< G 1; G 2> jG 1and G 2are context-free grammars such that L (G 1) L (G 2) g .

(b) L = f< M;n > jM is a Turing machine and n is a binary integer such that M accepts at least n words g.

(c) L = f< M;x ;n > jM is a Turing machine, x is a string to be input to M, and n is a binary integer such that M halts (either accepting or rejecting) on word x in at most n moves g.