Theory of Computation 2076 (new)
Attempt all the questions.
Section A
Long Answer Questions.
Attempt any Two questions. (2x10=20)
1. 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. (2+6+2)
2. 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. (2+4+4)
3. Define a Turing machine. Construct a TM that accept L = {wcwR | 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). (2+6+2)
Section B
Short Answer Questions.
Attempt any Eight questions. (8x5=40)
4. 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. (2+3)
5. Define Chomsky Normal Form and Greibach Normal Form in reference to CFG. Give a suitable example of each. (2.5+2.5)
6. Give the regular expressions for following language over alphabet {0, 1}. (2.5+2.5)
a. Set of all strings with 2nd symbol from right is 1.
b. Set of all strings starting with 00 or 11 and ending with 10 or 01.
7. Show that language L={0m1m | m>=1} is not a regular language.
8. Describe the Turing machines with multiple tape, multiple track and storage in state. (5)
9. Construct a NFA accepting language of {0, 1} with each string ending with 01 and convert it into equivalent DFA. (2+3)
10. 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. (3+2)
11. Define complexity of a Turing machine. Explain about big Oh, big Omega and big Theta notation used for complexity measurement. (1+4)
12. What do you mean by tractable and Intractable problems?Explain with reference to TM. (5)