Free grammatical context without context Free language

Question

How can I create a formal free context grammar for the following language:

{a i b j c k | i != j or j != k}

I have the following settings, but I can’t figure it out:

  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 (ie unequal b's and c's) Y -> aYb | bB | aA unequal a's b's 

Can someone help me understand and solve this problem?

Answer 1

Language L = {a i b j c k | i != j or j != k} L = {a i b j c k | i != j or j != k} can simply be written as L = L 1 UL 2 such that L 1 = {a i b j c k | i != j } L 1 = {a i b j c k | i != j } and L 1 = {a i b j c k | j != k } L 1 = {a i b j c k | j != k } .

In L ₁ there is no restriction on the character c only the condition numberOf(a) should not equal numberOf(b) . Or numberOf(a) numberOf(b) , or numberOf(a) < . numberOf(b) . So, the 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 the above grammar using E, we can generate an equal number a and b in the pattern a n Eb n , and then convert this sentimental form to a sentence form, either replace E with b or a , which causes a line to be generated in the form, so that a i b j with i != j using the variable X any number of c can be added to the template a i b j .

To understand this grammar, read: Tips for creating contextual free grammar and Why do I need terminals? Is my decision enough?

Similarly, for L ₂ there is no restriction on the character a only the condition numberOf(b) should not equal numberOf(c) . Or numberOf(b) numberOf(c) , or numberOf(b) < . numberOf(c) . So, the 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 these grammars, introducing a new initial variable S and two new production rules S => L1 | L2 S => L1 | L2 , we get a grammar for the language L = {a i b j c k | i != j or j != k} L = {a i b j c k | i != j or j != k} .

Answer 2

What if we changed the condition in this way, the language is still cf? {i = 2k+111}