Theory of Computation 2067-II

Attempt all the questions.

                                                                Group A                                                         (8x4=32)

1.  What is DFA? How it differ with a NFA? Explain.

2.  Give the DFA for language of strings over {0, 1} in which each strings end with 11.

3.  For a regular expression (a+b)*baa, construct ε-NFA.

4.  Define the term parse tree, regular grammar, sequential form and ambiguous grammar.

5.  Give the formal definition of NPDA. How it differs with DPDA? Explain.

6.  Construct a Turning Machine that accepts a language of strings over (a, b) with each string of even length. Show how it accepts string abab.

7.  Give the formal definition of Turning Machine. How it differs from PDA?

8.  Explain about the Unrestricted Grammar.

                                                                Group B                                                         (6x8=48)

9.  Show that a language L is accepted by some DFA if and only if L is accepted by some NFA.

10.  State and prove pumping lemma for regular language. Show by example how it can be used to prove a language is not a regular.

11.  Define Context Free Grammar. Given the following CFG.

S →0AS | 0, A → SIA| SS | 10

12.  Define deterministic PDA. Design a PDA that accept a language L = {anbn | n>0}. You may accept either by empty stack or by final state.

13.  Describe a Universal Turing Machine and its operations. What types of languages are accepted by Universal TM?

14.  Explain about the Chomsky Hierarchy of the language.