0
$\begingroup$

I have questions about how to put the grammar below in CNF - Chomsky Normal Form:

S ->aAa | bBb | ВВ;

A -> C;

B -> S | A;

C -> S | ε;

I did it like this:

  1. I eliminated empty productions:

S ->aAa | aa | bBb | bb| ВВ;

A -> C;

B -> S | A;

C -> S;

  1. I eliminated unit productions:

S ->aAa | aa | bBb | bb | ВВ;

A -> aAa | aa | bBb | bb | ВВ;

B -> Aa | aa | bBb | bb | ВВ;

C -> Aa | aa | bBb | bb | ВВ;

  1. I eliminated the useless variables (C), but it only becomes inaccessible after removing the unitary production of A ->C). Can anyone help me and tell me if this is right?
$\endgroup$

1 Answer 1

0
$\begingroup$

It is the case that $C$ becomes inaccessible, but your grammar isn't in normal form (yet). Rules like $S \to aAa$ or $S \to bb$ aren't allowed in CNF.

Also your grammar isn't equal to the original, since you forgot that $S$ is nullable when removing the $\varepsilon$ production (e.g. you could derive $S \Rightarrow BB \Rightarrow^* AA \Rightarrow^* CC \Rightarrow^* \varepsilon$ which isn't possible in your last grammar).

When bringing a grammar in CNF it's often a good idea to remove all $A \to B$ transitions first, and then remove the $\varepsilon$ transitions. So first start off by adding a new start variable $S'$

$$S \to S'$$ $$S' \to aAa | bBb | BB$$ $$A \to C$$ $$B \to S' | A$$ $$C \to S' | \varepsilon$$

then remove the $A \to C$ and $B \to A$ transition

$$S \to S'$$ $$S' \to aAa | bBb | BB$$ $$A \to S' | \varepsilon$$ $$B \to S' | \varepsilon$$

$C$ is now inaccessible, so we'll ignore it. Remove $A \to S'$ and $B \to S'$

$$S \to S'$$ $$S' \to aAa | aS'a | bBb | bS'b | BB | S'B | BS' | S'S'$$ $$A \to \varepsilon$$ $$B \to \varepsilon$$

remove the $\varepsilon$ transitions

$$S \to S' | \varepsilon$$ $$S' \to aa | aS'a | bb | bS'b | S' | S'S' | \varepsilon$$

remove $S' \to \varepsilon$ and $S' \to S'$

$$S \to S' | \varepsilon$$ $$S' \to aa | aS'a | bb | bS'b | S'S'.$$

This can now be brought into CNF

$$S \to S' | \varepsilon$$ $$S' \to AA | AX | BB | BY | S'S'$$ $$A \to a$$ $$X \to S'A$$ $$B \to B$$ $$Y \to S'B$$

as you should verify :]

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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