8

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?

Alan Moore
  • 73,866
  • 12
  • 100
  • 156
Light
  • 199
  • 1
  • 3
  • 9

1 Answers1

14

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

Community
  • 1
  • 1
Grijesh Chauhan
  • 57,103
  • 20
  • 141
  • 208
  • Adding one more related link [How to write grammar for formal language?](http://stackoverflow.com/questions/15559324/construct-grammar-given-the-following-language-an-bm-n-m-0-1-2-n-2/15578641?noredirect=1#comment28898425_15578641) – Grijesh Chauhan Oct 21 '13 at 05:04