toc important questions

toc important questions

1.Prove that ,if L is accepted by an NFA with -transitions, then L is accepted by an NFA
    without -transitions.
2.Prove that for every regular expression there exist an NFA with -transitions.
3. If L is accepted by an NFA with e-transition then show that L is accepted by an NFA
without e-transition.
4.conversion of NFA to DFA
5. Conversion of DFA into regular expression.
6.Leftmost and rightmost derivations.
7.Prove that for every derivations there exist a derivation tree.
8.Construction of reduced grammar
9.Chomsky normal form((cnf)
10.Conversion of CFL in GNF
11.Design a PDA that accepts the language {wwR | w in (0+1)*}.
R is power format..
12.Prove that if L is L(M2) for some PDA M2,then L is N(M1) for some PDA M1
13.If L is a context-free language, then prove that there exists a PDA M such that
L=N(M).
14. Conversion of PDA into CFL
15.state and prove pumping lemma for CFL.
16. Explain the various techniques for Turing machine construction
17. Briefly explain the different types of Turing machines
18. Design a TM to perform proper subtraction
19. Design a TM to accept the language L={0n1n | n>=1}
n in power format .
20.Explain how a TM can be used to determine the given number is prime or not?
21.State and explain RICE theorem
22.Define Lu and prove that Lu is recursive enumerable.
u in sub script
23. Define Ld and prove that Ld is undecidable
d in sub script
24.Prove that if a language L and its complement are both recursively enumerable, then L
is recursive.
25. Prove that the halting problem is undecidable
26. Prove that a language L is accepted by some epsilon -NFA if and only if L is accepted by
some DFA.
27.Construct DFA equivalent to the NFA tosome given
28. for a given epsilon -NFA.Compute the -closure of each state and find it’s
equivalent DFA
29. Prove that a language L is accepted by some DFA iff L is accepted by some NFA
30. Prove that if L=N(PN) for some PDA PN=(Q, , , N,q0,Z0),then there is a PDA PF
such that L=L(PF) where N,F and ) are sub scripts and in L=N(PN) la first N normal second n is the sub script
31. i)Obtain the chomsky normal form equivalent to the grammar.
S->AB|CA , B->BC|AB ,A->a ,C->aB|b
ii)Convert the grammar S->AB,A->BS|b,B->SA|a into greibach normal form
32.Define the language Lu.Check whether Lu is recursively enumerable or recursive.
Justify your answers where n and u are sub scripts