STUPIDSID
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
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