Reference no: EM133943896

Problem 1

Design a Turing Machine recognizing each of the following languages and draw its state diagram.

Note that transition function of each TM must read or write only one symbol from or to a single tape cell, and then move the head either left or right. Failure to follow this instruction will result in zero points for the problem.

(1) { w | w = a^(2n)b^n, n = 0 }
(2) { w | w = a^i b^j, i < j, i > 0 }
(3) { w | w = a^i b^j c^k, i < j < k, i = 1 }

Problem 2

Prove that language L = { a^n b^m a^n | m, n = 0 } is not regular.

Note that you must provide a clear and rigorous mathematical proof, free of any ambiguity or confusion.

Your explanation must include sufficient and convincing reasoning-not just a list of equations. Get expert assignment help online from PhD writers.

Attention: When using the Pumping Lemma to prove that a language is not regular, you should not
assume a specific pumping length, like 7. The pumping length p is given by the lemma and is arbitrary but fixed you must make your argument work for any such p.