0
$\begingroup$

I'm trying to figure out the intuition on creating a CFG in my head. I understand the idea of Grammar rules akin to "onions" with various layers throughout. For example, I was working on a problem earlier where I was to construct a CFG of $a^ib^jc^k$ with $i \ne j$ OR $j \ne k$. Obviously I separated the problem into two parts, $i$ not being $j$ and the other part being $j$ not being $k$. Taking the left part into account I wrote out the following:

$$\begin{align*} S &\to aSbTc \mid aS \mid bT \\ T &\to bTc \mid bc \\ D &\to cD \end{align*}$$ Am I correct in this for $i$ not being $j$ or is there something in my head thats wrong in thinking through this?

$\endgroup$
  • 1
    $\begingroup$ Taking a look at your first production rule, you could end up with the derivation S -> aSbTc -> aaSbTcbTc which no longer matches the desired pattern. I also don't see how the last production rule D -> cD is being used. $\endgroup$ – roctothorpe Apr 10 at 15:18
  • $\begingroup$ @roctothorpe Thanks for the suggested edit . I'm having a hard time figuring out how to rectify that, I thought the last production rule was to allow as many cs as possible? $\endgroup$ – Marorin Apr 10 at 15:39
  • $\begingroup$ @Marorin The production rule $D \to cD$ produces an arbitrary number of $c$'s, but $D$ remains part of the produced word, so the process never terminates. Even worse, $D$ is not even reachable from your other symbols, so the rule is completely redundant. I suggest you review the definition of a CFG and how productions work. $\endgroup$ – dkaeae Apr 10 at 16:06
  • $\begingroup$ @dkaeae So then the first rule should be aSbTc | a then and then second rule should be T -> bTcD | b and with D's rule changed to D --> Dc | c , that works, right? $\endgroup$ – Marorin Apr 10 at 17:13
  • $\begingroup$ Additionally, it's unclear from the question whether $i$, $j$, and $k$ are allowed to be 0. For example, should you be able to produce the string "$b$"? $\endgroup$ – roctothorpe Apr 10 at 18:39
1
$\begingroup$

The rules like "onions" with various layers that you describe in your question can be thought of as a build order for how you will construct a string -- eg. "first I will build this part of the string, and then I will build this other part" or "I need to build these two parts at the same time in order to ensure that they are synchronized".

A good general strategy for constructing a context free grammar is to determine this build order and then have a production rule that represents each stage and/or each possibility of your build order.

You should be able to point to each nonterminal and explain the "meaning" or type of string that nonterminal is trying to construct.

For the example of $a^ib^jc^k$ with $i \ne j$, one possible build order could be:

  1. Produce $a$'s and $b$'s in equal number (this is like $a^ib^j$ where $i = j$. Try writing a grammar for this first.)

  2. At some point, the number of $a$'s and $b$'s have to diverge, so pick either $a$ or $b$ and produce an unbounded number of that character (this is like $a^ib^j$ where $i \ne j$. Try taking the grammar you have from 1) and adding production rules to be able to do this.)

  3. Now just produce an unbounded number of $c$'s at the end. (this is the desired $a^ib^jc^k$ with $i \ne j$.)


A good question to ask yourself:

Why do we have to have more than one production rule to construct $a^ib^j$ where $i \ne j$? If I want the number of $a$'s and $b$'s to be equal, it makes sense that I'd have to build them at the same time, but if I want $i \ne j$, why can't I just do something like:

$S \rightarrow aS\ |\ Sb\ |\ \varepsilon$

which says "produce some number of $a$'s and then produce some number of $b$'s"?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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