Theory of Computation 2074
Attempt
all the questions.
Group
A
(8x4=32)
1. Convert the following NFA-ε into equivalent NFA without ε.
2. Find the regular expression describing following languages over alphabet {0, 1}*.
a) The language all strings containing at least two 0's.
b) The language of all strings containing both 00 and 010 as substring.
3. Construct FA recognizing the languages described by following regular expressions.
a) (10*+01*)11*
b) (0+1)*(01+1000)0*
4. What do you mean by a CFG in CNF? What are the criteria to be a CFG in CNF? Explain.
5. Define the term Regular Grammar. What is the relation of Regular Grammar with other grammars? Explain.
6. Define the universal Turing machine and describe its role.
7. Show that the complement of a recursive language is recursive.
8. Explain, how can you encode a Turing machine into universal language.
Group
B
(6x8=48)
9. Describe the extended transition function of a NFA. Construct a NFA accepting the language over {a, b}* with each strings containing three consecutive b's. Show by extended function that it accepts abbb.
10. Define the term immediate left recursion. How can you convert a grammar with immediate left recursion into equivalent grammar without left recursion? Remove left recursion from the following grammar.
11. Construct a PDA that accepts the strings of language L={ wwR | w is in {a, b}*}.
12. Describe multi tape Turing machine. Show that multi-tape Turing machine and one tape Turing machines are equivalent.
13. Define class P and NP with example. Show that: If P1 is NP complete and there is a polynomial time reduction of p1 to P2 then P2 is NP-complete.
14. Write short notes on (Any two):
a) Solvable vs Unsolvable problems
b) CNF Satisfiability
c) Recursive and Recursively Enumerable Languages