Given the ambiguous CFG : S → 01S1|SS|ϵ
I came up with the following CFG which I think is unambiguous:
S → 01X | 011X
X → 01X1 | ϵ
Is my CFG unambiguous and does it represent the same language?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
Let $D$ be the grammar, $S \mapsto01S1\mid SS\mid\epsilon$.
Then each word $w$ generated by $D$ is a mixture of equal number of $01$'s and $1$'s such that in any prefix of $w$ there are at least as many 1's as 0's but at most twice as many 1's as 0's.
Let $H$ be your grammar, $S \mapsto01X\mid011X$ and $X\mapsto 01X1\mid ϵ$.
Then each word generated by $X$ is some number of 01's followed by the same number of 1's. So each word $w$ generated by $H$ starts with 01 or 011, followed by some number of 01's, followed by the same number of 1's.
Both $D$ and $H$ are CFGs. While $D$ is ambiguous as illustrated by $011\ \ 011011=011011\ \ 011$, $H$ is unambiguous.
The word 010111011 is generated by $D$ but not by $H$. The word 01011 is generated by $H$ but not by $D$. Hence, the language generated by $D$ and the language generated by $H$ are not the same.
It should not be hard to prove the various claims in the above paragraphs. Yuval Filmus' idea to treat 01 as one symbol might be helpful.
Is the language generated by $D$ inherently ambiguous? Here is the spoiler.
No. In fact, there is a deterministic grammar $S \mapsto \epsilon\mid 01S1S $. The language is actually isomorphic to the celebrated dyck language.