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 |

→q_{0} |
{q_{0},q_{1}} |
q_{1} |
{} |

q_{1} |
{q_{2}} |
{q_{1},q_{2}} |
{} |

*q_{2} |
{q_{0}} |
{q_{2}} |
{q_{1}} |

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 0

^{n}1^{n}^{n}
10 M

4(a)
Draw a state diagram and construct a regular expression corresponding to the following state transition table.

State →*q _{1} |
0 q _{1} |
1 q _{2} |

q_{2} |
q_{3} |
q_{2} |

q_{3} |
q_{1} |
q_{2} |

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

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

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