Michael Sipser Edition 3 Exercise 2 Question 9 (Page No. 155)

Question

Give a context-free grammar that generates the language $A=\{a^{i}b^{j}c^{k}\mid i=j$ $\text{or}$ $ j=k$ $\text{where}$ $ i,j,k\geq 0\}.$ Is your grammar ambiguous$?$ Why or why not$?$

Answer 1

A is union of two languages $a^nb^nc^m \cup a^mb^nc^n$

PDA for this language is NPDA. So it is ambiguous

Comments

YOU can have a string where i=j=k which can be created by  both

a^nb^nc^m   or a^mb^nc^n

---

How does that answers whether the language is ambiguous or not?

---

S->A|B

A->aAb|abC

B->bBc|Xbc

C->cC|c

X->aX|a

The above is the grammar,So we can choose any one of the path from S either A or B ,which will give us

a^nb^nc^m   or a^mb^nc^n    where m=n.

---

This grammar is incorrect as it will accept strings in which c comes before b also.