Scribd
Upload
56 views

CFG Practice Sheet

CFG practice sheet

Uploaded by

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

CFG Practice Sheet

CFG practice sheet

Uploaded by

bijan das
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 2

1.

Construct both the left-most and right-most derivation trees for the string (abbba)
S→aAB∣bBA
A→aA∣bB→bB∣a
2. S→AB∣BAA→aA∣aB→bB∣b
Provide the left-most and right-most derivation sequences for the string (aabbb)
3. S→aSb∣SS∣ϵ
Is this grammar ambiguous? If yes, show how it generates ambiguity using the string
aabb.
4. E→E+E∣E∗E∣(E)∣id
Prove that this grammar is ambiguous by showing different parse trees for the
expression id + id * id.
5. S→S+S∣S∗S∣(S)∣a
Demonstrate that the grammar is ambiguous by finding multiple parse trees for the
expression (a + a) * a.
6. S→AB∣B
A→aB→C
C→bC∣ϵ
Simplify the above context free grammar
7. S→AB∣C
A→aA∣B
B→b
C→cC∣D
D→ϵ
Simplify the above context free grammar
8. S→AB∣a
A→BC∣b
B→b
C→c
Convert the above grammar to CNF
9. S→aA
A→Bb
B→b
Convert the above grammar to CNF
10. S→S+S∣a
Convert the above grammar to GNF
11. S→A∣AB
A→aA∣ϵ
B→bB∣b
Convert the above grammar to GNF
12. L={a^nb^nc^n∣n≥1} Prove that this language is not context-free.
13. L={a^mb^nc^(m+n)∣m,n≥1} Prove that this language is not context-free.
14. S→ASB∣a
A→aA∣a
B→bB∣b
Create a PDA that accepts the language represented by this CFG, which generates
strings in the form ambna^m b^n.

15. Construct a PDA for the given CFG, and test whether 010000 is acceptable by this
PDA.

S → 0BB

B → 0S | 1S | 0

16. Construct a CFG for the WW^R PDA, and test whether 0110 is acceptable by CFG
or not.
17. Construct a CFG

M=({q_0, q_1},{a,b},{a,z_0},δ,q_0,Z_0,φ )

δ (q_0,a,z_0)=(q_0,az_0); δ (q_0,a,a)=(q_0,aa)

δ (q_0,b,a)=(q_1,a); δ (q_1,b,a)=(q_1,a)

δ (q_1,a,a)=(q_1,∊); δ (q_1,∊,z_0)=(q_1,∊)

You might also like