1 (a)
Consider the following grammer G={V, T, P, S}, V={S, X}, T{0, 1} and productions P are

S→0| 0X1 | 01S1

X→ 0XXI| 1S

S is start symbol. Show that above grammer is ambiguous.

S→0| 0X1 | 01S1

X→ 0XXI| 1S

S is start symbol. Show that above grammer is ambiguous.

5 M

1 (b)
State and prove the halting problem.

5 M

1 (c)
Convert following ε-NFA to NFA without ε.

5 M

1 (d)
Prove that Language L={0

^{n}10^{n}for n=0, 1, 2, ....} is not regular.
5 M

2 (a)
Consider the following grammer G=(V, T, P, S), V={S, X, Y}, T{a, b} and productions P are

S→XYX

X→aX|ε

Y→bY|ε

Convert this grammer in Chomsky Normal Form (CNF).

S→XYX

X→aX|ε

Y→bY|ε

Convert this grammer in Chomsky Normal Form (CNF).

10 M

2 (b)
Design DPDA to acept language L={x∈{a, b}* | N

_{a}(x)>N_{b}(x)}, N_{a}(x)>N_{b}(x) means number of a's are greater than number of b's in string x:
10 M

3 (a)
Design Turing machine to accept the language L=set of string with equal number of a's and b's.

10 M

3 (b)
Design the DFA to accept the language containing all the strings over ∑={a, b, c} that starts and ends with different symbols.

10 M

4 (a)
Design Moore Machine for the input from (0+1+2)* which print the residue modulo 5 of the input treated as ternary number.

10 M

4 (b)
State and prove pumping lemma for context free language.

10 M

5 (a)
Convert the following grammer into finite automata.

S→aX | bY | a | b

X→aS | bY | b

Y→aX | bS.

S→aX | bY | a | b

X→aS | bY | b

Y→aX | bS.

5 M

5 (b)
Compare recursive and recursively enumerable languages.

5 M

5 (c)
State and prove Rice's theorem.

10 M

6 (a)
Write regular expression for the following languages.

language containing all the string in which every pair of adjacent a's appears before any pair of adjacent b's, over the alphabet ∑{a, b}:

ii) language containing all the string in which all possible combination of a's and b's is present but strings does not have two consecutive a's, over the alphabet ∑{a, b}.

language containing all the string in which every pair of adjacent a's appears before any pair of adjacent b's, over the alphabet ∑{a, b}:

ii) language containing all the string in which all possible combination of a's and b's is present but strings does not have two consecutive a's, over the alphabet ∑{a, b}.

10 M

6 (b)
Write short note on 'Unversal Turing Machine'.

5 M

6 (c)
Explain variation and equivalences of Turing machine.

10 M

More question papers from Theoretical Computer Science