16 MARK QUESTIONS
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.If L is accepted by an NFA with ε-transition then show that L is accepted by an NFA
without ε-transition
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.
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
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.
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
26. Prove that a language L is accepted by some ε-NFA if and only if L is accepted by some DFA.
27. Construct DFA equivalent to the NFA given
| s | i | 0 | 1 |
| p | {p,q} | p |
| q | r | r |
| r | s | - |
| s | s | s |
28. Consider the following ε-NFA.Compute the ε-closure of each state and find it’s
equivalent DFA
| s | i | ε | a | b | c |
| p | {q} | {p} | ф | ф |
| q | {r} | ф | {q} | ф |
| r | ф | ф | ф | {r} |
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).
31. i)Obtain the chomsky normal form equivalent to the grammar.
S->AB|CA , B->BC|AB ,A->a ,C->aB|b (6)
ii)Convert the grammar S->AB,A->BS|b,B->SA|a into greibach normal form.(10)
32. Define the language Lu.Check whether Lu is recursively enumerable or recursive.
Justify your answers.
BOOK REFERED
1.Introduction to automata theory,languages,and computation
by John E.Hopcroft,Jeffery D,Ullman
No comments:
Post a Comment