2
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Essam
    Jan 14, 2023 at 6:17
  • $\begingroup$ @Essam, yes, that would be okay. $\endgroup$
    – D.W.
    Jan 14, 2023 at 6:20

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.