MORE IN Theoretical Computer Science
MU Computer Engineering (Semester 4)
Theoretical Computer Science
December 2016
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) Design a DFA over an alphabet ∑={a, b} to recognize a language in which every 'a' is followed by 'b'.
5 M
1(b) Give formal definition of a Push Down Automata.
5 M
1(c) State and explain the power and limitations of a Turing machine.
5 M
1(d) Design a mealy machine to determine the residue mod 3 of a binary number.
5 M

2(a) Convert the following NFA to an equivalent DFA
 State a b c →q0 {q0,q1} q1 {} q1 {q2} {q1,q2} {} *q2 {q0} {q2} {q1}
10 M
2(b) State and explain pumping lemma for regular languages. Using pumping lemma prove that the language $$L=\left \{ o^n1^n|n\geq 0 \right \}$$/ is not regular.
10 M

3(a) Design a Turing machine that computers a function f(m,n)=m+n i.e. addition of two integers.
10 M
3(b) Design a Turing machine to accept the language 0n1nn
10 M

4(a) Draw a state diagram and construct a regular expression corresponding to the following state transition table.
 State →*q1 0 q1 1 q2 q2 q3 q2 q3 q1 q2
10 M
4(b) State and explain decision properties of regular languages
10 M

5(a) i) Convert the following CFG to GNF
S→AA|a
A→SS|b
10 M
5(b) Design a PDA correponding to the to the grammar S→aSA |ε
A→bB
B→b
10 M

Write a short note any two Q6.(a,b,c,d)
6(a) Recursive and Recursively Enumerable Languages.
10 M
6(b) Chomsky Hierarchy
10 M
6(c) Rice's Theorem
10 M
6(d) Halting problem
10 M

More question papers from Theoretical Computer Science