Theory of Computation 2067

Attempt all the questions.

                                                                Group A                                                         (8x4=32)

1. Define finite Automata with ɛ moves.Is ɛ NFA has more computation power than DFA?

2. GIve the DFA accepting the string over {a, b} such that each string doesn't start with ab.

3.  Give the regular expression for the following languages.

        a. L={SS ∈ {a, b}* and S starts with aa or b and does not contains substring bb.

        b. L={S|S ∈ {0, 1}* and 0 occurs in pairs if any and ends with 1.

4.  Convert following regular grammar into Finite Automata.

5. Convert following grammar into equivalent PDA

6.  What is a multi track Turing Machine? How it differs with single track machine?

7.  Construct a Turing Machine that accepts the language of palindrome over {a, b}* with each string of odd length.

8.  What is an algorithm? Explain on the basis of Church Hypothesis.

                                                                Group B                                                         (6x8=48)

9.  How a ε-NFA can be converted into NFA and DFA? Explain with a suitable example.

10. Find the minimum state DFA equivalent to the following  DFA.

11.  Show that a language L is accepted by some DFA if and only if L is accepted by s.

12.  Define the language of PDA that accepts by Final State. Explain how a PDA accepting empty stack can be converted into a PDA by final state.

13.  Explain about multi tape TM. Show that every language accepted by a multi-tape Turning Machine is also accepted by one tape Turning Machine.

14.  Write short notes on:

a.               Decidable Vs Un-decidable problems.

b.              Unrestricted Grammar

c.               NP-completeness

d.              CNF-SAT Problem.