2
$\begingroup$

I'm trying to prove that the following CFG can be converted to a CNF:

S -> aAB
A -> aAa
A -> bb
B -> a

Here below is how I've managed so far:

Step 1: add a new start state

S0 -> S
S -> aAB
A -> aAa
A -> bb
B -> a

Step 2: remove epsilon rules

There are no such rules in this CFG.

Step 3: remove non-terminal to non-terminal rules

S0 -> aAB
S -> aAB
A -> aAa
A -> bb
B -> a
Step 4: make right-hand-side not contain more than $2$ non-terminals or $1$ terminal:
S0 -> BC
S -> BC
A -> BF | EE (A -> aAa and A -> bb in one line)
B -> a
C -> AB
E -> b
F -> AB

So this is where I got confused. I have now both C and F that go to AB. If I've done this correctly that would mean that either C or F can simply be removed. Or, of course, I've done something wrong in this procedure.

$\endgroup$
  • 3
    $\begingroup$ "I'm trying to prove that the following CFG can be converted to a CNF:" -- Every CFG can; it's called Chomsky Normal Form for a reason. Just follow the algorithm from that proof. $\endgroup$ – Raphael Sep 19 '16 at 19:43
6
$\begingroup$

You're right to be cautious, but there is nothing wrong.

A context-free grammar is in Chomsky Normal Form if and only if every rule is of the form:

A → BC,  or
A → a,   or
S → ε,   where S is the start symbol.

Consider the grammar

S → TU
S → UT
T → a
U → a

Is this a valid context-free grammar in Chomsky Normal Form?

Yes, it is. Each rule is of one of the allowed forms.

But - you say - T and U have the exact same rules; one can be replaced with the other!

Congratulations: you have invented a normal form! A grammar is in Byfjunarn Normal Form if and only if it has no two different nonterminals for which the rules have the exact same right hand sides.

This is clearly a normal form: in fact, normalizing grammars into this form is so easy that we do it routinely, without even thinking about it.

But the algorithm you're using to bring arbitrary grammars into Chomsky Normal Form doesn't. Why should it? Grammars can be in Chomsky Normal Form without being in Byfjunarn Normal Form; the example proves it. Yes, it would be easy to modify the algorithm to bring grammars not only into Chomsky Normal Form, but also into Byfjunarn Normal Form. But nobody asked it to. Except you.

Just let the poor algorithm go about its ways. You know what to do once it's finished :-)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for the answer. Was both fun to read and very informatic. I cannot upvote it yet but i will as soon as i get enough points. Cheers! $\endgroup$ – Byfjunarn Sep 20 '16 at 9:08
0
$\begingroup$

Here is Swaira Shabbir's image answer, converted into mathjax:

$$ \begin{align} S&\rightarrow aAB\\ A&\rightarrow aAa\\ A&\rightarrow bb\\ B&\rightarrow a\\ \end{align} $$ CFG-to-CNF
$\underline{Step\text{ }1}$: Not hold, as there is no 'S' on right side of any production.
$\underline{Step\text{ }2}$: No Epsilon rules here i.e. No Useless, Null & Unit Productions.
$\underline{Step\text{ }3}$: Non terminal -> 2 Non terminals
Non Terminal -> one terminal
Production that does not follow these rules, convert their right side to uppercase & add new productions. $$ \begin{align} X&\rightarrow a\\ Y&\rightarrow b\\ S&\rightarrow XAB\\ A&\rightarrow XAX\mid YY\\ B&\rightarrow a\\ \end{align} $$ $\underline{Step\text{ }4}$: Reduce length of right side of productions to '2' terminals by introducing new productions. $$ \begin{align} X&\rightarrow a\\ Y&\rightarrow b\\ R&\rightarrow XA\\ S&\rightarrow RB\\ A&\rightarrow RX\mid YY\\ B&\rightarrow a\\ \end{align} $$ So required CNF Form is:

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ You don't need to show us the Mathjax source; we can click 'edit' and see it. The answer seems to be missing something at the end, since it doesn't appear to tell us what the final CNF form is. $\endgroup$ – D.W. Mar 21 at 16:15
-2
$\begingroup$

1) no empty production 2) no unit production 3) convert all mix term and terminal greater than one into capital

S->AAB A->AAB/BB B->a A->a

4) Reduce the length of each non terminal upto 2 and add new rule S->TB A->TB/BB B->a A->a T->AA (new rule)

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ I don't see how this answers the question. A little explanation would make this answer much clearer. In particular, what does this answer add to the existing answer above? $\endgroup$ – Discrete lizard Feb 11 '19 at 9:25
-3
$\begingroup$

Rules for conversion of CFG to CNF https://www.geeksforgeeks.org/converting-context-free-grammar-chomsky-normal-form/

Here is the solution of question:solution

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ Please see this MathJax tutorial so that you can write your answer instead of posting a picture of a handwritten solution. Also, try to make your solutions stand alone and not require links to external sources for them to be understood. $\endgroup$ – Throckmorton Feb 21 at 16:51

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.