Given the grammar:

$S \to AS\mid \varepsilon$
$A \to A1\mid 0A1 \mid \varepsilon$

Generate a new unambiguous grammar that generates the same language as the grammar above.

I have no idea how to make it unambiguous, I have proven already that the given language has two leftmost derivations for the string 01101.


Your grammar generates the language $L(A)^*$, where $$ L(A) = \{0^i 1^j : j \geq i\}. $$ You can generate $L(A)$ unambiguously in many ways. Two options are:

  1. Use $0^i 1^j = 0^i 1^i 1^{j-i}$.
  2. Use $0^i 1^j = 0^i 1^{j-i} 1^i$.

Given that, the current productions for $S$ will already generate $L(A)^*$ unambiguously.


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.