Theory of Computation TU Board 2080 (new course) question paper

Describe the extended transition function of NFA. Construct a NFA, using transition table and transition diagram , over {0, 1} that accept the string having substring 01 and ends with 1. Show the acceptance of 0111.

Define CFG. Construct a CFG that generates the language of all palindromes over {a,b} that do not contain the substring aa. Show the leftmost derevation and construct the equivalent parse tree for string babbbab.

How Turing Machine is used as a computing function? Construct a TM for simulating a function f(x) = 2x for x = {1}. Itetrate the TM for input 11 and generate the output 1111.

Differentiate Kleen closure from positive closure. Compute positive and Kleen closure of {ab}.

Design a Melay machine over {a, b} that generates output 'A' if the input string ends with aa else output 'B' if the string ends with bb.

Construct regular expression over {1,2,….9} that represents

1. strings of even numbers with length 4 starting with 2 and ending with 8.
2. strings starting with odd numbers and ending with even numbers.

Prove that th language L ={a^n b^n c^n | n≥0} is not a context free grammar.

Construct a PDA that accepts string over Σ ={a,b} that contains equal number of a's followed by equal number of b's. Show acceptance of aabb and aab.

Describe how multi-stack TM is different from the semi-infinite tape TM?

What is intractability? Define time and space complexity of turing machine.

How conversion of PDA to CFG done ? Illustrate with example.

State Arden's theorem. Convert following DFA into its regular expression using Arden theorem.

[figure in the original paper]