HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Equivalent unambiguous grammar

Submitted by: @import:stackexchange-cs··
0
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.

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:

  • 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.