Theory of Computation 2078

Section A

Long Answer Questions.

Attempt any Two questions.    (2x10=20)

1. Give the formal definition of DFA and NFA. How NFA can be converted into eqivalent DFA? Explain with suitable example.

2. Find the minimum state DFA for the given DFA below.

3. Construct a Turing Machine that accepts the language of odd length strings over alphabet {a, b}. Give the complete encoding for this TM as well as its input string w = abb in binary alphabet that is recoginzed by Universal Turing Machine.

Section B

Short Answer Questions.

Attempt any Eight questions.     (8x5=40)

4. Define the term alphabet, prefix and suffix of string, concatenation and Kleen closure with example.

5. Give the regular expressions for the following language over alphabet{a,b},

    a. Set of all strings with substring bab ar abb

    b. Set of all strings whose 3^rd symbol is 'a' and 5^th symbol is 'b'

6. Show that L = {aⁿ | n is a prime number} is not a regular language.

7. Explain about the Chomsky's Hierarchy about the language and grammars.

8. Define a Push Down Automata. Construct a PDA that accept L = {aⁿbⁿ | n>=0}.

9. Convert the following grammar into Chomsky Normal Form.

        S → abSb | a | aAb

        A → bS | aAAb | ε

10. Define Turing Machine and explain its different variations.

11. What do you mean by computational Complexity? Explain about the time and space complexity of a Turing machine.

12. Explain the term Intractability. Is SAT problem is intractable? Justify.