# Duplicate rules in CFG

Suppose I have the following CFG that I would like to bring to CNF

S -> TA | bA | Ab | b

A -> Aa|a

T -> Ab


Then I have two options to get rid of the nonsolitary terminal a in Aa

1 - Make a new nonterminal K and introduce the rule

The grammar in this case becomes

K->a

S -> TA | bA | Ab | b

A -> AK|a

T -> Ab


2 - Observe that A->a already and use it

The grammar in this case becomes

S -> TA | bA | Ab | b

A -> AA|a

T -> Ab


My intuition is that both should be correct since I don't see that changing a nonterminal's name would change the language the grammar generates but I am not entirely sure.

Thanks.

In this case, both are correct, but in general, you should use method 1.

For example, suppose that you had

$$A \to Aa|a|b.$$

You might be tempted to say that we have $$A \to a$$ already, so let's just use $$A$$ instead of creating a new non-terminal, and convert this to

$$A \to AA|a|b.$$

This would be an incorrect transformation, because originally $$A$$ generates the language $$a,b,aa,ba,aaa,baa,\cdots$$, and after the (incorrect) conversion, $$A$$ generates $$a,b,aa,ab,ba,bb,aaa,aab,\cdots$$

So, use method 1. Method 1 is always correct. It is just a "happy accident" that method 2 happens to work in this case, but in general, it often won't work.

• That's intuitive, thanks. One more question to make sure I really understand this. Suppose I had two rules F->ABD|... and G->ABD|...when reducing RHSs into binary it would be okay this time to let X->AB once and use it for both, right? Jan 14 at 6:17
• @Essam, yes, that would be okay.
– D.W.
Jan 14 at 6:20