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?

  • 1
    $\begingroup$ Have you tried proving your claims? This is how we know that a mathematical statement is true. $\endgroup$ – Yuval Filmus Oct 16 '18 at 5:29
  • $\begingroup$ Your grammar generates $01$, which is not in the original language. $\endgroup$ – Yuval Filmus Oct 16 '18 at 5:44
  • $\begingroup$ Tip: Replace $01$ with $($ and $1$ with $)$. $\endgroup$ – Yuval Filmus Oct 16 '18 at 5:44
  • 1
    $\begingroup$ The original grammar seems faulty; it generates $\emptyset$ since we can't get rid of any $S$. $\endgroup$ – Raphael Oct 16 '18 at 5:44
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Oct 16 '18 at 5:45

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.