16 marks
1.Prove that ,if L is accepted by an NFA with _-transitions, then L is accepted by an NFA
without _-transitions.
Refer page no:26,Theorem 2.2
2.Prove that for every regular expression there exist an NFA with _-transitions.
Refer page no:30,Theorem 2.3
3.Construct the NFA with _-transitions from the given regular expression.
_ If the regular expression is in the form of ab then NFA is
a b
_ If the regular expression is in a+b form then NFA is
_ a _
_ b _
_ If the regular expression is in a* form then NFA is
_ a _
4.conversion of NFA to DFA
_ Draw the NFA’s transition table
_ Take the initial state of NFA be the initial state of DFA.
_ Transit the initial state for all the input symbols.
_ If new state appears transit it again and again to make all state as old state.
_ All the new states are the states of the required DFA
_ Draw the transition table for DFA
_ Draw the DFA from the transition table.
_
5.Conversion of DFA into regular expression.
Arden’s theorem is used to find regular expression from the DFA.
using this theorem if the equation is of the form R=Q+RP,we
can write this as R=QP*.
_ Write the equations for all the states.
_ Apply Ardens theorem and eliminate all the states.
Theory of Computation 22
_ Find the equation of the final state with only the input symbols.
_ Made the simplifications if possible
_ The equation obtained is the required regular expression.
6.Leftmost and rightmost derivations.
If we apply a production only to the leftmost variable at every step to derive the
required string then it is called as leftmost derivation.
If we apply a production only to the rightmost variable at every step to derive the
required string then it is called as rightmost derivation.
Example:
Consider G whose productions are S->aAS|a , A->SbA|SS|ba.For the string
w=aabbaa find the leftmost and rightmost derivation.
LMD: S=>aAS
=>aSbAS
=>aabAS
=>aabbaS
=>aabbaa
RMD: S=>aAS
=>aAa
=>aSbAa
=>aSbbaa
=>aabbaa
7. Prove that for every derivations there exist a derivation tree.
Refer page no: 84,Theorem 4.1
8.Construction of reduced grammar.
??Elimination of null productions
- In a CFG,productions of the form A->_ can be eliminated, where A is
a variable.
??Elimination of unit productions.
- In a CFG,productions of the form A->B can be eliminated, where A
and B are variables.
??Elimination of Useless symbols.
- these are the variables in CFG which does not derive any terminal or
not reachable from the start symbols. These can also eliminated.
-
9. Chomsky normal form(CNF)
If the CFG is in CNF if it satisfies the following conditions
- All the production must contain only one terminal or only two
variables in the right hand side.
Example: Consider G with the production of S->aAB , A-> bC , B->b, C->c.
G in CNF is S->EB , E->DA , D-> a , A->FC , F-> b , B->b , C-> c.
10.Conversion of CFL in GNF.
Refer page no: 97,Example 4.10
Theory of Computation 23
11.Design a PDA that accepts the language {wwR | w in (0+1)*}.
Refer page no:112,Example 5.2
12. Prove that if L is L(M2) for some PDA M2,then L is N(M1) for some PDA M1.
Refer page no:114,Theorem 5.1
13.If L is a context-free language, then prove that there exists a PDA M such that
L=N(M).
Refer page no: 116,Theorem 5.3
14.Conversion of PDA into CFL.
Theorem: refer page no:117
Example: refer page no :119
15.State and prove the pumping lemma for CFL
Refer page no: 125,Theorem 6.1
16.Explain the various techniques for Turing machine construction.
- storage in finite control
- multiple tracks
- checking off symbols
- shifting over
- subroutines.
For explanation refer page no 153-158
17.Briefly explain the different types of Turing machines.
- two way finite tape TM
- multi tape TM
- nondeterministic TM
- multi dimensional TM
- multihead TM
For explanation refer page no 160-165
18.Design a TM to perform proper subtraction.
Refer page no: 151,Example 7.2
19Design a TM to accept the language L={0n1n | n>=1}
Refer page no:149,Example 7.1
20. Explain how a TM can be used to determine the given number is prime or not?
It takes a binary input greater than 2,written on the first track, and determines
whether it is a prime. The input is surrounded by the symbol $ on the first track.
Theory of Computation 24
To test if the input is a prime, the TM first writes the number 2 in binary on the
second track and copies the first track on to the third. Then the second track is subtracted
as many times as possible, from the third track effectively dividing the third track by the
second and leaving the remainder.
If the remainder is zero, the number on the first track is not a prime.If the
remainder is non zero,the number on the second track is increased by one.If the second
track equals the first,the number on the first track is the prime.If the second is less than
first,the whole operation is repeated for the new number on the second track.
21.State and explain RICE theorem.
Refer page no: 188,Theorem 8.6
22.Define Lu and prove that Lu is recursive enumerable.
Refer page no: 183,Theorem 8.4
23. Define Ld and prove that Ld is undecidable.
Refer page no: 182.
24.Prove that if a language L and its complement are both recursively enumerable, then L
is recursive.
Refer page no: 180,Theorem 8.3
25.Prove that the halting problem is undecidable.
Refer page no: 187
.
BOOK REFERED
1.Introduction to automata theory,languages,and computation
by John E.Hopcroft,Jeffery D,Ullman