SRM University 2007 B.Tech Computer Science and Engineering BANK : THEORY OF COMPUTATION - exam paper

4) If L is accepted by a DFA, then show that L is denoted by a regular expression.
5) Construct an NDFA equivalent to (0+1)*(00+11).
6) Construct a regular expression corresponding to the transition diagram in the subsequent figure.
F={q1},initial state={q1}
States\inputs 0 1
q1 q1 q2
q2 q3 q2
q3 q1 q2



7) If M1 is a meanly machine, then show that there is a Moore machine M2 equivalent to M1.
8) Constuct Moore machine from the provided meanly machine.
Initial state={q0}

States\inputs 0 1 x y
q0 {p0}
{p1} {p0,p1} -
p0 {p0} {p1} {p1} {p0}
p1 {p0} {p1} {p0} {p1}

9) Show that the set L = { 0i 1i / i =1} is not regular
10)Show that the set L = { oi2 / i is an integer , i =1 } is not regular
11)Show that L={0m 1n 0 m+n}is not regular.
12)Construct minimized DFA from the provided NDFA.
States\inputs 0 1
q0 {q0,q1} {q0,q3}
q1 {q2} -
q2 - -
q3 - {q4}
q4 - -
13)Construct an NDFA without € transitions from the provided NDFA with e transition.
F={q2},initial state={q0}
States\inputs 0 1 2 e
q0 q0 - - q1
q1 - q1 - q2
q2 - - q2 -

UNIT-II

1) Let a be CFG and let A? w in a., then S.t that there is a LMD of ‘w’.
2) Let G=(V,T,P,S)be a CFG. Then prove that s? a iff there is a destination tree in grammar G with yield a.
3) If G is the grammar s –>sbs/a,show that G is ambiguous.
4) discuss in detail the ambiguity in CFG.
5) Prove that every non empty CFL is generated by a CFG with no useless symbols.
6) Let G=(V,T,P,S) be a CFG with L=L(G).Then show that there exists a CFG G¹ with L(G¹)=L-{e}has no useless symbols or e-productions.
7) Prove that for any CFL without e is described by a grammar with no useless symbols, €-productions or unit production.
8) Prove that for any CFL without e is generated by a grammar in which every production is of the form A–>BC OR
A–>a(CNF).
9) Prove that for every CFL without ‘e’ can be generated by a grammar for which every production is of the form A–>aa , where ‘A’ is a variable ,’a’ is a terminal &’a’ is eternize of variables (possible empty)(GNF).
10)Find a grammar in CNF equivalent to S–>aAD;A–>ab/bAB;
B–>b;D–>d.
11)Find a grammar in CNF equivalent to S->aAbB;A–>aA/a;
B–>bB/b.
12)Construct a grammar in GNF equivalent to the grammar
S–>AA/a;A–>SS/b.
13)Convert to GNF the grammar G-C{A1,A2,A3},{a,b},{P,A1},where P consists of the subsequent :
A1–>A2A3;A2–>A3A1/b;A3–>A1A2/a;




UNIT -III


1) If L is L(M2) for a few PDA M2,then show that L is N(M1)has identical PDA M1.
2) If L is N(M1) for a few PDA M1 ,then show that L is L(M2)for a few PDA M2.
3) If L is CFL, then prove that there exists a PDA M such that L=N(M).
4) If L is N(M) for a few PDA M,then show that L is CFL.
5) Construct when CFG G which accepts N(M),when M=C{q0,q1},{0,1},{z0,z1},?,q,?)and ‘?’is provided by:
? (q0, 0,z0)=(q0,zz0); ?(q1,1,Z)=(q1,e)
? (q0, 0,z)=(q0,ZZ); ?(q1, e,Z)=(q1, e)
? (q0,1,z)=(q1, e); ?(q1, e,z0)=(q1, e)
6) Construct a PDA for the language L={wwR/w in (0+1)*}
7) Construct a PDA for the language L={wcwR/w in (0+1)*}
8) Show that L={ aibjcidj/i=1, j=1}is not a CFL
9) Show that L={on1n two n/n=1}is not a CFL.
10)Show that L={ aibjck/i?j,j?k& i?k} is not a CFL.



Unit IV

1) Design a turing machine M to implement the function “multiplication”using the subroutine “copy”.
2) Design a TM to calculate proper subtraction m-n.
3) Design a TM to accept the language L={0n1 n/n=1}
4) Construct a TM to recognize the language L={ 02n/n=0}
5) Enumerate the different techniques adopted for the construction of a TM.
6) Explain finite control can be treated as storage for a finite amount of info.
7) Illustrate with an example the techniques of creating the tape to have multiple tracks.
8) Illustrate with example the techniques of checking off symbols.
9) Construct a part of TM to shift non blank symbol 2 cells to the right end. support that tape does not contain blanks ranging from non blanks.
10) Prove that if L is recognized by a TM with a 2 way infinite tape iff it is recognized by a TM with a 1 way infinite tape



UNIT V

1)Discuss in detail about universal TM.
2)Show that the complement of a recursive language is recursive.
3)Show that Lu is recursively enumerable but not recursive.
4)Show that Ld is not recursively enumerable.
5)If a language L and its complement L’ are both recursively enumerable, then show that L and hence L’ are recursive.
6)Prove that there exists a recursively enumerable language whose complement is not recursively enumerable.
7)Prove that any non-trivial property of the recursively enumerable languages is undecidable.(Rice’s theorem).
8)Prove that Halting issue is undecidable.

Earning:   Approval pending.