Formal Context Free Grammar From Context Free Language

Question

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 1

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 L₁ 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 L₂ 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}.