STUPIDSID
Solve any one question from Q.1(a,b) &Q.2(a,b)
1(a)
Construct FA that accepts even number of zeros & odd number of ones.
6 M
1(b)
Write formal definition of regular expression with suitable example. State Arden's theorem and its use.
4 M
2(a)
Construct a Moore machine to find out the residue-modulo-3 for binary number.
6 M
2(b)
Define regular sets. List out closure properties of regular sets.
4 M
Solve any one question from Q.3(a,b) &Q.4(a,b)
3(a)
Define the following and give apporpriate examples
i) Derivation tree
ii) Context free grammar.
i) Derivation tree
ii) Context free grammar.
6 M
3(b)
Conevert right linear grammar to its equivalent left linear grammar.
S→bB
B→bC
B→aB
B→ b
C→a
S→bB
B→bC
B→aB
B→ b
C→a
6 M
4(a)
Construct a DFA equivalent to the following grammar
S→S10|0
S→S10|0
6 M
4(b)
Write a short note on the applicaitons of CFG.
4 M
Solve any one question from Q.5(a,b) &Q.6(a,b)
5(a)
Design a PDA that checks wellformedness of parentheses. Simulate PDA for (( ) (( )) ).
8 M
5(b)
Define and compare DPDA and NPDA. Justify that NPDA is more powerful than DPDA.
8 M
6(a)
Construct a PDA for the language generated by the following grammar.
S→aB|bA
A→bAA | a | aS
B→b |bS| aBB
S→aB|bA
A→bAA | a | aS
B→b |bS| aBB
8 M
6(b)
Define post machine. Compare FA, PDA and post machines.
8 M
Solve any one question from Q.7(a,b) & Q.8(a,b)
7(a)
Write a short note on:
i) Church Turing Hypothesis
ii) Post correspondence problem.
i) Church Turing Hypothesis
ii) Post correspondence problem.
8 M
7(b)
Design a Turing Machine to recognize the language \( L = \left \{ 1^{n} 2^{n}3^{n}|n> =1\right \}. \)/ Simulate TM for "112233".
10 M
8(a)
Design a Turing machine that accepts \( L = \left \{ 0^{n} 1^{n}|n< =1\right \}. \)/ Simulate TM for "00011".
10 M
8(b)
Explain the following for a TM
i) Power of TM over finite state machine
ii) Universal TM
i) Power of TM over finite state machine
ii) Universal TM
8 M
Solve any one question from Q.9(a,b) & Q.10(a,b)
9(a)
Write a short note on decidable problems concerning
i) Context free languages
ii) Turing machines
i) Context free languages
ii) Turing machines
8 M
9(b)
What is reducibility? What are undecidable problems? Describe at least four undecidable problems in case of CFGs.
8 M
10(a)
Describe post correspondence problem. PCP is an unsolvable problem. Justify.
8 M
10(b)
What are recursive and recursively enumerable languages? What is the relation between them?
8 M
More question papers from Theory of Computation