Scribd
Upload
8 views2 pages

Theory of Computation Unit III Question Bank

This document is a question bank for Unit III of the Theory of Computation course at MET’s Institute of Engineering, covering various topics such as context-free grammar, ambiguous grammar, Chomsky Normal Form (CNF), and regular grammar. It includes questions on defining concepts, simplifying grammars, converting grammars to CNF and Greibach Normal Form (GNF), and constructing DFAs from grammars. The document serves as a study guide for students in the Computer Engineering department.

Uploaded by

shlkhairnar
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
8 views2 pages

Theory of Computation Unit III Question Bank

This document is a question bank for Unit III of the Theory of Computation course at MET’s Institute of Engineering, covering various topics such as context-free grammar, ambiguous grammar, Chomsky Normal Form (CNF), and regular grammar. It includes questions on defining concepts, simplifying grammars, converting grammars to CNF and Greibach Normal Form (GNF), and constructing DFAs from grammars. The document serves as a study guide for students in the Computer Engineering department.

Uploaded by

shlkhairnar
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Theory of Computation Question Bank Unit III

MET’s Institute of Engineering, BKC, Nashik.

Department of Computer Engineering.


Theory of Computation Unit III Question Bank
1.
2. Define Context free Grammar & give the CFG for the following languages :
a. (011+1)*(01)* b. 0i 1i+k 0k where i, k>=0
3. What is the ambiguous grammar? Show that the grammar below is ambiguous, & find the
equivalent un ambiguous grammar.
a. s→ss│a│b b. s→ABA, A→aAb│Є, B→bB
4. Determine whether the given grammar is unambigneous or not for the string aaabbabbba.
Find left most derivation and right most derivation. Also draw the parse tree.
s→aB│bA A→aS│a│bAA , B→bS│aBB│b

3a. What steps are required for simplifying the given CFG? Explain with example.

5. Simplify the following grammar


a. S→Ab , A→a, B→C│b, C→D, D→E, E→a
b. S→0A0│1B1│BB, A→C, B→S│A, C→S│ Є
c. S→ ASB│ Є, A→aAS│a, B→SbS│A│bb
6. What is CNF? How do we convert a CFG to CNF? Explain.
7. Check whether the given grammar is in CNF. If not then find its equivalent CNF.
a. S→bA│aB, A→bAA│aS│a, B→aBB│bS│b
b. S→PQP, P→0P│ Є , Q→1Q│ Є
8. Convert the following grammar to CNF
a. aab│Aba, B→Ac
b. S→AACD, A→aAb│ Є, C→aC│a, A→ aDa│bDb│ Є
9. What is GNF? What are the steps to convert a CFG to GNF? Explain.
10. Construct a equivalent GNF grammar for the given grammar.
a. S→AA│a, A→SS│b
b. E→E+T│ T, T→T*F│F, F→(E)│a
c. S→AB, A→BSB│BB│b, B→aAb│a
11. Give chomsky classification for grammar.

Subject Teacher Yawalkar Prashant M.


Theory of Computation Question Bank Unit III

12. What is regular Grammar? What are the different forms of regular grammar?
13. Give the Right Linear Grammar & Left linear grammar for the following DFA shown in
fig1 and fig2.

Fig 1 Fig 2

14. Convert the following right Linear Grammar to DFA


a. S→ 0A│1B, A→ 0C|1A|0, B→1B|1A|1, C→0|0A
b. S→ bB, B→ bC|aB|b, C→a
15. Construct a DFA for the following left linear grammar
a. S→Ca|Bb, C→Bb, B→Ba|b
b. S→B1|A0|C0, B→B1|1, A→ A1|B1|C0|0, C→A0
16. Find an equivalent left linear grammar for the given right linear grammar
a. S→10A|01, A→00A|1,
b. S→bB|b, B→bC|aB|b, C→a
c. S→ 0A|1B, A→ 0C|1A|0, B→1B|1A|1, C→0|0A
17. Find an Equivalent right linear grammar for the given left linear grammar
a. S→C0|A0|B1, A→A1|C0|B1|0, B→B1|1, C→A0
18. Construct the right Linear grammar corresponding to the regular expressions.
a. R=(0+1)1*(1+(01)*)
b. R=(1+(01)*)1*(0+1)
19. Explain the closure properties of context free languages
20. List and explain the applications of CFG.
21. Define Concurrent Grammar.

Subject Teacher Yawalkar Prashant M.

You might also like