2010,2009 Qpapers

2010


11a
1. DFA for string with 3 consec 0s.
2. DFA vs NFA with eg

b. NFA to DFA
http://i26.lulzimg.com/62a021.png



12a
1. Find language accepted by

	0    	1
------------------
q0	q2   	q1
q1	q3	q0
q2	q0	q3
q3	q1	q2



2. R is  RE  PT  there exists NFA with e that accepts L(R)
is the lang L={a^nb^n | n>=1} is Regular

b:

1. minimal DFA for RE { (b|a)*baa}
2. PT regular sets are closed under substitiution

13 a

1. Let G be the grammar
F ->aB / bA
A-> a/aF/bAA
B->b/bF/aBB

for string baabbabba
LMD,RMD,Parse tree

2. DPDA with eg.

13b

1. Construct PDA for {WCW^r | (0+1)* }
2. Let L be a context normal form grammar equivalent to CFG

14 a
1. Obtain Gribach Grammar
F-> AA|0
A->AA|1

2. Turning machine for L={1^n0^n | n>=1 }

14b

1. Explain closure props of CFG
2. Const Turing maching {WW^r | {0+1}*

15a
1. Tractable vs Intractable with eg
2. Haltin probelm explain

15b
1. Post correspondence with eh
2. Any 4 NP complete probs


2 marks     //Some 2 marks were left out becoz they were simple...
1 inductive proof
2 Pumping lemma
3 CFG for {a^nb^n |n>=1}
4 is E->E+E|id is ambiguous
5 turing machine
6 L={a^nb^nc^n n>1} is CFG?

7 what is Rennumerable lang
8 decidable vs undecidable



NoV dec 2009

11a
1. PT for evry NFA there exists DFA that sims NFA
2. find DFA equaivalent to NFA

11b
1. PT for every RE gamma there exits alpha NFA with e-trnasitions that accepts L(gamma)
2. construct E-NFA for RE (0+1)*010(11)*

12a
1. S->a iff there is derivation for CFG which yields a
2. consider G={ {S},{a,b}, {P},{S} }
where P consits of
S->aAS/a
A->SbA/SS/bA

derivation tree for aabbaa

12b
1. find CNF
S->aBB
A->aB/bAB
B-> b

2
Grammar to GNF
A1->A2A3
A2->A3A1/b
A3-> A1A2/a

13a
1. equivalence between PDA with emty and final stake
2. NPDA acception {WW^r | (0+1)* }

13b
1. PT every language N(M) recognized by a PDA M is a CFL


14a
1. design a TM recognize strings with even no. of 1s
14a
2. Explain how multiple tracks can be used to test given positive int is prime or not

14b
1. TM do multiplication with subtractive copy
2. ST if L is accepted by multi tape TM then ti is accepted by single tape TM

15a
1. design language Ld show that Ld is not RE
15a
2. Union of 2 Rec langs is Rec.

15b
1. Define Lu is RE but not Rec


2 marks
1. define DFA
2. Check if strings ababba,baab are accepted by DFA
3.Define CFG
4. if G is a grammar
S->Sba/a
PT G is ambiguous
5. define ID of a PDA
6. check if CFL Lp {a^nb^n | n>=0) is a Deterministric CFL
7. how TM can be rregarded as a computing devive to compute integer function
8. use of check off symbol in TM
9. define recursive R and RE language
10 rice theorem