patternMinor
Equivalent unambiguous grammar
Viewed 0 times
grammarequivalentunambiguous
Problem
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.
$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.
Solution
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:
Given that, the current productions for $S$ will already generate $L(A)^*$ unambiguously.
$$
L(A) = \{0^i 1^j : j \geq i\}.
$$
You can generate $L(A)$ unambiguously in many ways. Two options are:
- Use $0^i 1^j = 0^i 1^i 1^{j-i}$.
- 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.
Context
StackExchange Computer Science Q#106837, answer score: 2
Revisions (0)
No revisions yet.