Theory of Computation TU Board 2076 question paper

Define the NFA with ε-transition and ε-closure of a state. Show that for every regular expression r, representing a language L, there is ε-NFA accepting the same language. Also convert regular expression (a+b)ab into equivalent Finite Automata.

How can you define the language accepted by a PDA? Explain how a PDA accepting language by empty stack is converted into an equivalent PDA accepting by final state and vice-versa.

Define a Turing machine. Construct a TM that accept L = {wcw^R | w∈(0, 1) and c is ε or 0 or 1. Show that string 0110 is accepted by this TM with sequence of Instantaneous Description (ID).

Give the formal definition of DFA. Construct a DFA accepting all strings of {0, 1} with even number of 0's and even number of 1's.

Define Chomsky Normal Form and Greibach Normal Form in reference to CFG. Give a suitable example of each.

Give the regular expressions for following language over alphabet {0, 1}.

1. Set of all strings with 2^nd symbol from right is 1.
2. Set of all strings starting with 00 or 11 and ending with 10 or 01.

Show that language L={0^m1^m | m>=1} is not a regular language.

Describe the Turing machines with multiple tape, multiple track and storage in state.

Construct a NFA accepting language of {0, 1} with each string ending with 01 and convert it into equivalent DFA.

Construct a PDA accepting language over {0, 1} representing strings with equal no of 0s and1s. Show by sequence of IDs that 0101 is accepted by this PDA.

Define complexity of a Turing machine. Explain about big Oh, big Omega and big Theta notation used for complexity measurement.

What do you mean by tractable and Intractable problems? Explain with reference to TM.