1. Define CFG.2.Find L(G)where G=({S},{0,1},{S->0S1,S->ε},S).
2. Define derivation tree for a CFG(or)Define parse tree.
3. Construct the CFG for generating the language L={anbn/n>=1}.
4. Let G be the grammar S->aB/bA,A->a/aS/bAA,B->b/bS/aBB.for the string aaabbabbba find the left most derivation.
5. Let G be the grammar S->aB/bA,A->a/aS/bAA,B->b/bS/aBB.obtain parse tree for the string aaabbabbba.
6. For the grammar S->aCa,C->aCa/b.Find L(G).
7. Show that id+id*id can be generated by two distinct leftmost derivation in the grammar E->E+E | E*E | (E) | id .
8. For the grammar S->A1B,A->0A | ε, B-> 0B | 1B| ε,give leftmost and rightmost derivations for the string 00101.
9. Find the language generated by the CFG G=({S},{0,1},{S->0/1/ ε, S->0S0/1S1},S).
10 obtain the derivation tree for the grammar G=({S,A},{a,b},P,S) where P consist of S->aAS / a, A->SbA / SS / ba.
11 Consider the alphabet Σ={a,b,(,),+,*, ., ε} .Construct the context free grammar that generates all strings in Σ* that are regular expression over the alphabet {a,b}.
12 Write the CFG to generate the set {am bn cp | m + n=p and p>=1}.
13 Construct a derivation tree for the string 0011000 using the grammar S->A0S |0 | SS , A-> S1A | 10.
14 Give an example for a context free grammar.
15 Let the production of the grammar be S-> 0B | 1A, A-> 0 | 0S | 1AA, B-> 1|1S | 0BB.for the string 0110 find the right most derivation.
16 What is the disadvantages of unambiguous parse tree. Give an example.
17 Give an example of PDA.
18. Define the acceptance of a PDA by empty stack. Is it true that the language accepted by a PDA by empty stack or by that of final state are differentlanguages.
20 What is additional featurePDA has when compared with NFA? Is PDA superior over NFA in the sense of language acceptance? Justify your answer.
21. Explain what actions take place in the PDA by the transitions (moves) δ(q,a,Z)={(p1,γ1),(p2, γ2),…..(pm, γm)} and δ(q, ε,Z)= {(p1,γ1),(p2,γ2),…..(pm,γm)}.
22. What are the different ways in which a PDA accepts the language? Define them. Is a true that non deterministic PDA is more powerful than that of deterministic PDA? Justify your answer.
23. Explain acceptance of PDA with empty stack.
24. Is it true that deterministic push down automata and non deterministic push down automata are equivalent in the sense of language of acceptances? Justify your answer.
25. Define instantaneous description of a PDA.
26. Give the formal definition of a PDA.
27. Define the languages generated by a PDA using final state of the PDA and empty stack of that PDA.
28. Define the language generated by a PDA using the two methods of accepting a language.
29. Define the language recognized by the PDA using empty stack.
2. Define derivation tree for a CFG(or)Define parse tree.
3. Construct the CFG for generating the language L={anbn/n>=1}.
4. Let G be the grammar S->aB/bA,A->a/aS/bAA,B->b/bS/aBB.for the string aaabbabbba find the left most derivation.
5. Let G be the grammar S->aB/bA,A->a/aS/bAA,B->b/bS/aBB.obtain parse tree for the string aaabbabbba.
6. For the grammar S->aCa,C->aCa/b.Find L(G).
7. Show that id+id*id can be generated by two distinct leftmost derivation in the grammar E->E+E | E*E | (E) | id .
8. For the grammar S->A1B,A->0A | ε, B-> 0B | 1B| ε,give leftmost and rightmost derivations for the string 00101.
9. Find the language generated by the CFG G=({S},{0,1},{S->0/1/ ε, S->0S0/1S1},S).
10 obtain the derivation tree for the grammar G=({S,A},{a,b},P,S) where P consist of S->aAS / a, A->SbA / SS / ba.
11 Consider the alphabet Σ={a,b,(,),+,*, ., ε} .Construct the context free grammar that generates all strings in Σ* that are regular expression over the alphabet {a,b}.
12 Write the CFG to generate the set {am bn cp | m + n=p and p>=1}.
13 Construct a derivation tree for the string 0011000 using the grammar S->A0S |0 | SS , A-> S1A | 10.
14 Give an example for a context free grammar.
15 Let the production of the grammar be S-> 0B | 1A, A-> 0 | 0S | 1AA, B-> 1|1S | 0BB.for the string 0110 find the right most derivation.
16 What is the disadvantages of unambiguous parse tree. Give an example.
17 Give an example of PDA.
18. Define the acceptance of a PDA by empty stack. Is it true that the language accepted by a PDA by empty stack or by that of final state are differentlanguages.
20 What is additional featurePDA has when compared with NFA? Is PDA superior over NFA in the sense of language acceptance? Justify your answer.
21. Explain what actions take place in the PDA by the transitions (moves) δ(q,a,Z)={(p1,γ1),(p2, γ2),…..(pm, γm)} and δ(q, ε,Z)= {(p1,γ1),(p2,γ2),…..(pm,γm)}.
22. What are the different ways in which a PDA accepts the language? Define them. Is a true that non deterministic PDA is more powerful than that of deterministic PDA? Justify your answer.
23. Explain acceptance of PDA with empty stack.
24. Is it true that deterministic push down automata and non deterministic push down automata are equivalent in the sense of language of acceptances? Justify your answer.
25. Define instantaneous description of a PDA.
26. Give the formal definition of a PDA.
27. Define the languages generated by a PDA using final state of the PDA and empty stack of that PDA.
28. Define the language generated by a PDA using the two methods of accepting a language.
29. Define the language recognized by the PDA using empty stack.
No comments:
Post a Comment