I need to generate unambiguous grammar to access the language L= { a^i b^j c^k | i, j, k ≥ 0 , i = j or i = k }
What I already have is:
S : X | Y
X : TC
T : aTb | ԑ
C : cC | ԑ
Y : aYc | F
F : bF | ԑ
but this grammar is ambiguous, it can recognize the strings with equal number of a,b,c in two different ways. Is there any better suggestion to make it unambiguous?
S : X | Y | Z
X : aXb | ԑ
Y : aYc | F
Z : Zc | X | ԑ
F : Fb | ԑ
The above has less rules and produces correct strings but I admit it's still ambiguous.
The grammar of the language L in the question can be divided into two sub-grammars producing following strings: a^i b^i c^j and a^i b^j c^j and intersection of these two will result in this kind of expressions: a^i b^i c^i. It can be proved that if intersection of two grammars produces this kind of expressions then the grammar is inherently ambiguous: http://en.wikipedia.org/wiki/Ambiguous_grammar#Inherently_ambiguous_languages