### CS-501-CBGS

B.Tech., V Semester

Examination, May 2018

Choice Based Grading System (CBGS)

Theory of Computation

1.a) Explain Deterministic and nondeterministic finite automata with example.

Ans.

b) Explain application of pumping lemma.

2.a) Construct a NDFA accepting all string in {a,b} with either two consecutive a’s or two consecutive b’s.

Ans. Click here.

b) Find the grammar in Chomsky Normal form equivalent to S–>aAD;A->aB/bAB;B->b,D->d.

Ans. Click here.

3. Explain the following:

a) Regular grammars

Ans.

b) Context free grammars

c) Derivation trees.

4.a) Construct a grammar in GNF which is equivalent to the grammar S->AA / a , A ->SS / b.

b) Define deterministic Push Dawn Automata DPDA. It is true that DPDA and PDA are equivalent in the sense of language acceptance in concern? Justify your answer.

5.a) Demonstrate the working of your TM with an example.

b) Explain in detail notes on universal Turing machines with example.

6.a) Describe the recursively Enumerable Language with example.

b) Construct a PDA for set of palindrome over the alphabet {a,b} L(M)={WcWR}.

7.a) Give a detailed description of ambiguity in Context free grammar.

b) Explain Vertex conver problem and Hamiltonian path problem.

8. Explain the following:

a) NP complete and NP hard

b) Traveling salesman problem