Im having some problems with a qeuestion regarding converting a context free grammar to chomsky normal form.

I have S -> abC | babS | de C -> aCa |b

I know what to do with the case of aCa and de and b but im not sure how to handle the abC case or the babS case. I believe that chomsky normal form is supposed to have outputs of only 2 characters. so with something like aCa you make and output aa and have A->a and create another nonterminal? X -> SA but I dont know how im supposed to handle the abC case or the babS case.

  • 2
    $\begingroup$ What research have you done? Have you studied how to convert a grammar to Chomsky to normal form? It sounds like not. So, I suggest you read up on this in Wikipedia or in your textbook.... $\endgroup$ – D.W. Nov 25 '13 at 3:41
  • 2
    $\begingroup$ I recommend that you read about how to convert a grammar into Chomsky normal form. There are standard techniques for doing so. For instance, they're most likely covered in your textbook. Wikipedia also explains a procedure for converting any grammar to Chomsky normal form. That should be sufficient to help you solve your exercise on your own. $\endgroup$ – D.W. Nov 25 '13 at 3:42

Let's work it out through the conversion algorithm given in Wikipedia.

$S \to abC \mid babS \mid de$
$C\to aCa \mid b$

  1. Introduce $S_0$:
    $S_0 \to S$
    $S \to abC \mid babS \mid de$
    $C\to aCa \mid b$
  2. remove $\epsilon$ rules: there are no $\epsilon$ rules, so nothing changes.
  3. eliminate unit rules: Originally, there are none, but we added one, namely $S_0\to S$. Since it's the only one, we'll deal with it later (after $S$ is already in CNF). This will be done by adding, for any rule $S\to V_iV_j$, the rule $S_0 \to V_iV_j$. But let's first complete the conversion.
  4. replace all other rules into normal form: we take each transition which is not in the correct form and replace it with $N\to V_iV_j$, introducing new non-terminals $V_1, V_2,...$ as needed:
    • $S\to ab C$ $\Longrightarrow$ $S\to V_1 C$ setting $V_1 \to ab$. The new $V_1$ is not in CNF, but can easily be converted to CNF by re-defining it as $V_1\to AB$ with $A\to a$, $B\to b$.
    • $S\to babS$ $\Longrightarrow$ $S\to V_2S$ adding $V_2 \to bab$. Now $V_2$ is not in CNF, so we change it to $V_2 \to V_3B$ adding $V_3\to BA$. (skipping a trivial step here)
    • $S\to de$ is almost CNF. We change it to $S\to DE$ and add $E\to e$, and $D\to d$.
    • $C\to aCa$ $\Longrightarrow$ $C\to AV_4$ where $V_4 \to CA$.
    • $C \to b$ is already in CNF.

so we end up with:
$S_0 \to S$
$S\to V_1 C$
$S\to V_2S$
$S\to DE$
$C\to AV_4$
$C \to b$
$V_1 \to AB$
$V_2 \to V_3B$
$V_3 \to BA$
$V_4 \to CA$
and $A\to a$, $B\to b$, $D\to d$, $E\to e$.

Finally, we need to deal with the unit rule $S_0 \to S$. As said, we will replace the $S$ in the right-hand-side with the "content" of S. That is, we remove that unit rule and add instead:
$S_0 \to V_1C \mid V_2S \mid DE$.


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.