Converting to CFG from a CFL? [duplicate]

Question

I am trying to learn CFG. Now to make a CFG from a CFL it is really difficult for me.

Is there any simple rule or steps so that I can easily find a CFG for a CFL. I am trying to solve one problem for generating a CFG. The Problem statement is to find a CFG that generates the following CFL: $$\{a^ib^jc^k \mid i,j,k\geq 0\text{ and } i\neq j\text{ or } i\neq k\}$$

Now I am trying hard to find one but I am not successful. Is there any easy approach to construct a CFG for a CFL?

Answer 1

As @babou indicated, there's no algorithmic way to produce a CFG from a description of a CFL, meaning that the problem is more art than science. There are, though, some idioms that turn out to be useful in practice.

Idiom 1. First, ignore the condition $i,j,k\ge 0$ for the moment, since that condition usually turns out to be easy to express in a grammar.

Idiom 2. See if the language can be expressed as the union or concatenation of simpler languages (intersection and complement are of less help, since CFLs aren't closed under these operations). In your case, the or in your original statement is a clue. Express your language as the union of simpler languages: $$ \{a^ib^jc^k\mid i\ne j\}\cup\{a^ib^jc^k\mid, i\ne k\} $$

Idiom 3. If you have an inequality, as you do here, note that we can express the $i\ne j$ condition as another or, namely $i\ne j\Longleftrightarrow (i > j) \lor (i< j)$, so $$ \{a^ib^jc^k\mid i\ne j\}=\{a^ib^jc^k\mid i>j\}\cup\{a^ib^jc^k\mid i<j\} $$ Idiom 4. Separate the problem into concatenated pieces if possible. For this example, we note that the $a^ib^j$ part will have nothing to do with the $c^k$ part, so we might start out grammar with the production $S\rightarrow TU$, where $T$ will generate the $a^ib^j$ and $U$ will generate the $c^k$ part. The latter is easy, and now we fill in the omission in idiom 1, writing $U\rightarrow cU\mid \epsilon$ (since if the requirement had been, say, $k>0$ we could just use $U\rightarrow cU\mid c$).

Idiom 5. Now what to do with the $a^ib^j$ part, where $i>j$? Simple, write it as $a^na^jb^j$ for some $n>0$. To get an arbitrary number of a's in front, we can use $T\rightarrow aT$. Eventually we'll stop generating a's and will switch to the matching a's and b's, using yet another variable $V$, so we'll have $T\rightarrow aT\mid aV$.

Idiom 6. Finally, to generate a matching number of a's and b's we work from the inside out, placing one of each on the ends, so we'll have $V\rightarrow aVb\mid \epsilon$. This is very common when dealing with CFLs.

Finally, then, we have the grammar for one part of our language: $$\begin{align} S&\rightarrow TU\\ T&\rightarrow aT\mid aV\\ U&\rightarrow cU\mid\epsilon\\ V&\rightarrow aVb\mid\epsilon \end{align}$$ Of course, we still have a lot of work to do, but the rest is largely of the same form. Yes, it is complicated; all I can offer is that it gets easier with practice. Eventually, you might get to the stage where you'll often say "I've seen a problem like this before; maybe I can do something similar".

Answer 2

Unfortunately there is no simple algorithmic rule for this type of problem. You have to understand properties of CF languages and how they can be expressed with grammars.

Here is a further hint for your problem.

Can you write a grammar for the language

$L_1= \{a^ib^jc^k \mid i,j,k\geq 0\text{ and } i\neq j\}$

However, Rick Decker is right. I tend to see the building of grammars as a black art. But any art, however black, has its own know-how, techniques, heuristics, and incantations which may or may not work depending on various factors (else it would not be an art :).

This leads me to idiom 2bis, which could be added to the others:

Idiom 2bis When the conditions of the original statement, setting constraints between the variables, include an and connective (explicit, or implicit as in $a<b<c$), it may be a clue that you have an intersection of two languages. Then if it is clear that one of them is a regular language, you should concentrate on the other which probably carries the CF difficulties of the problem. The reason is that CF languages are closed under intersection with regular set: given a CF grammar for one and a regular grammar (or FSA) for the other, it is easy to get algorithmically a grammar for the intersection. However, if both arguments of the intersection are CF, there is a good possibility that the language you are considering is not CF since the intersection of two CF languages is not in general CF ... though it may be CF in some cases.

For example, in the language considered in the question, the condition $i,j,k\geq 0$ is anded with other conditions, but this is not really a problem, because it defines no constraint between $i$, $j$, and $k$. However, the two inequalities define such constraints. And it is actually the case that if the or were replaced by an and, the language would no longer be CF.