6
$\begingroup$

This question already has an answer here:

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?

$\endgroup$

marked as duplicate by Raphael Nov 17 '14 at 18:05

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

migrated from cstheory.stackexchange.com Nov 17 '14 at 16:01

This question came from our site for theoretical computer scientists and researchers in related fields.

  • $\begingroup$ There is no standard way to do that, since a "minor" change in the conditions would make the language non-CF, such as replacing or by and. But this remark should help you. The or hints to union. $\endgroup$ – babou Nov 17 '14 at 10:10
7
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ If you have a somewhat general, structured approach (or set of "rules"?) to finding grammars, maybe our reference question can profit from your answer? $\endgroup$ – Raphael Nov 17 '14 at 18:06
  • 1
    $\begingroup$ @Raphael. This answer should be augmented with several more idioms I omitted before it qualifies as a righteous reference, but I'll consider it if I can find the time. $\endgroup$ – Rick Decker Nov 17 '14 at 20:52
  • 1
    $\begingroup$ Cool, thanks! (I think it'd be fair to post what you have now and insert "ToDos" -- it'd help more than not. Kaveh's had ToDos in that huge reference answer of his for ages... ;)) $\endgroup$ – Raphael Nov 17 '14 at 23:03
  • $\begingroup$ I added one such idom in my answer. That is actually a very good idea. cf @Raphael $\endgroup$ – babou Nov 28 '14 at 12:02
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Addendum: then construct a grammar for $L_2 = \{a^ib^jc^k | i, j, k \ge 0$ and $i \ne k\}$. Then just make a new start variable consisting of $S \rightarrow S_1 | S_2$. $\endgroup$ – Ryan Nov 17 '14 at 17:20
  • $\begingroup$ @Ryan That was supposed to be only a hint. People have to do some thinking by themselves if they are to learn anything. $\endgroup$ – babou Nov 17 '14 at 17:23
  • 1
    $\begingroup$ Feel free to add a collection of idioms to our reference question! Such heuristics are definitely missing there. $\endgroup$ – Raphael Nov 28 '14 at 13:53

Not the answer you're looking for? Browse other questions tagged or ask your own question.