MORE IN Theoretical Computer Science
MU Computer Engineering (Semester 4)
Theoretical Computer Science
December 2014
Total marks: --
Total time: --
INSTRUCTIONS
(1) Assume appropriate data and state your reasons
(2) Marks are given to the right of every question
(3) Draw neat diagrams wherever necessary

1 (a) Give chomsky hierachy of grammar with examples.
5 M
1 (b) State and explain any 5 closure properties of regular language.
5 M
1 (c) Compare recursive and recursively enumerable language.
5 M
1 (d) State and prove equivalence of NFA and DFA.
5 M

2 (a) Design a DFA to accept strings over the alphabet set {a, b} that begin with 'aa' but not end with 'aa'.
10 M
2 (b) Covert (0+$$\epsilon$$) (1 0)*($$\epsilon$$+1) into NFA with $$\epsilon$$-moves and hence obtain a DFA.
10 M

3 (a) Design a MOORE and MEALY machine to decrement a binary number.
10 M
3 (b) Give statement of pumping lemma for regular sets and hence prove that {w c wR|W? (a+b)*} is not regular where wR is reverse of w.
10 M

4 (a) Obtain leftmost derivation, rightmost derivation and derivation tree for the string "cccbaccba". The grammar us S→Ssa|SSb|c
10 M
4 (b) Design Turing machine as generator to add two binary numbers and hence simulate for "110+10". Hint: Assume two way infinite tape.
10 M

5 (a) Design a PDA to accept language {an-1 b2n+1 | n≥1}.
10 M
5 (b) Convert the below given grammar to Chomsky Normal Form (CNF) and Griebach Normal Form (GNF) E→E+E|E*E|(E)|id
Consider "id" as a single terminal/symbol.
10 M

6 (a) Design a Turing machine as acceptor for the language
{an bm|n, m≥0 and m≥n}.
10 M
6 (b) Design PDA to check even parentheses over Σ={0,1}.
10 M

More question papers from Theoretical Computer Science