Formal Context Free Grammar From Context Free Language
How can a formal context free grammar be generated for the following language:
{ai bjck | i != j or j != k}
I have following productions but can't understand it:
S->AX | YC unequal b’s c’s or a’s b’s
A-> aA | e 0 or more A’s
C -> cC |e 0 or more c’s
B -> bB | e 0 or more B’s
X -> bXc | bB | cC equal b’s, c’s then 1+ b’s,
1+C’s (i.e. unequal b’s and c’s)
Y -> aYb | bB | aA unequal a’s b’s
Can anyone help me to understand and solve this problem?
Answer
The language L = {ai bj ck | i != j or j != k} can be simply written as L = L1 U L2 such that L1 = {ai bj ck | i != j } and L1 = {ai bj ck | j != k }.
In L1 there is no constraint on symbol c only condition is numberOf(a) should not be equals to numberOf(b). Either numberof(a) > numberOf(b) or numberof(a) <.numberOf(b). So grammar for this language should be:
L1 => EX // L1 is start variable
E => aEb | A | B
X => C | ^
A => aA | a
B => bB | b
C => cC | c
In above grammar using E we can generate equal number of a and b in the pattern of anEbn, then to convert this sentimental from into sentence form either E has to replaced by B or A that causes generate a string in the form such that ai bj with i != j , Using variable X any number of c can be suffixed to the pattern ai bj.
To understand this grammar read: Tips for creating Context free grammar and Why the need for terminals? Is my solution sufficient enough?
Similarly for L2 there is no constraint on symbol a only condition is numberOf(b) should not be equals to numberOf(c). Either numberof(b) > numberOf(c) or numberof(b) <.numberOf(c). So grammar for this language should be:
L2 => YF // L2 is start variable
F => bFc | B | C
Y => A | ^
A => aA | a
B => bB | b
C => cC | c
Now using both of this grammar an introducing a new start variable S and two new production rules S => L1 | L2 we gets grammar for language L = {ai bj ck | i != j or j != k}.