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