Answer any one question from Q1 and Q2

1 (a)
Write the formal definition of the following:

i) Finite Automata

ii) E-closure

i) Finite Automata

ii) E-closure

4 M

1 (b)
Using pumping lemma for the regular sets prove the language [ L={ a^{i^2} | i ge | } ] is not regular.

6 M

2 (a)
Construct the minimum state automation equivalent to the transition diagram given as below:

6 M

2 (b)
Construct Regular Expression for the following transition diagram using Arden's theorem.

4 M

Answer any one question from Q3 and Q4

3 (a)
Construct the parse trees for the strings using specified derivation for the given grammar G. [ G=({ S,A,B}, {a,b}, P, {S}) \ egin {align*} P= {&S o aB, S o bA} \ & A o a, A o aS, A o bAA \ &B o b, B o bS, B o aBB end{align*} ] Strings: i) aaabbb (rightmost derivation)

ii) aababb (rightmost derivation).

ii) aababb (rightmost derivation).

4 M

3 (b)
Describe CFG, Chomsky Normal Form and Greibach Normal Form, with suitable examples.

6 M

4 (a)
Remove Unit-productions from the given grammar.

P = { S → ABA|BA|AA|AB|A|B

A → aA|a

B → bB|b

}

P = { S → ABA|BA|AA|AB|A|B

A → aA|a

B → bB|b

}

4 M

4 (b)
Define ambiguous grammar.

1) S ? 0S|S|1S0S| ∈

2) S → AA

A → aAb|bAa| ∈

Consider above grammars. Test whether these grammars are ambiguous.

1) S ? 0S|S|1S0S| ∈

2) S → AA

A → aAb|bAa| ∈

Consider above grammars. Test whether these grammars are ambiguous.

6 M

Answer any one question from Q5 and Q6

5 (a)
Construct a PDA that accepts the following language using CNF. [ L={a^{2n} | n ge 0 }. ]

8 M

5 (b)
Write formal definition of PDA. Explain its elements. What are different types of PDA? What are the applications of PDA?

8 M

6 (a)
Design a PDA accepting {a

^{n}b^{m}a^{n}|m,n≥1} simulate a PDA for the string 'aabaa'.
8 M

6 (b)
Define post machine. Explain its elements. Show that the post machine is more powerful that PDA.

8 M

Answer any one question from Q7 and Q8

7 (a)
Design a TM which accepts all strings of the form a

^{n}b^{n}for n≥1 and rejects all other strings. Draw the transition diagram. Simulated TM for some string.
10 M

Write short notes on:

7 (b) (i)
Universal Turing Machine.

4 M

7 (b) (ii)
Multi-tape Turing Machine.

4 M

8 (a)
Design a TM to add two unary numbers.

8 M

8 (b)
Design a TM that recognize a string containing aba as a substring.

6 M

8 (c)
Write a short note on Non deterministic Turing Machine.

4 M

Answer any one question from Q9 and Q10

9 (a)
Show that for two recursive languages L

i) L

ii) L

_{1}&L_{2}, each of the following is recursivei) L

_{1}∪ L_{2}ii) L

_{1}∩ L_{2}
8 M

9(b)
Define decidability. How to prove the given language is undecidable problems.

8 M

10 (a)
Write a short note on halting problem of Turing Machine.

8 M

Explain the following

10 (b)(i)
Recursive sets.

4 M

10 (b)(ii)
Turing reducibility.

4 M

More question papers from Theory of Computation