Repeated rules in Chomsky normal form

301 Views Asked by At

My question is simple, when you're converting a grammar to CNF, what happens when a rule begins to repeat multiple times?

¿It's good to end with rules like $U_1 \rightarrow SB, U_2 \rightarrow SB, etc...$?, Or is it better to use a single variable in this case?

An example I saw:

We have...

$S_0 \rightarrow ASB|SB|AS$

$S \rightarrow ASB|SB|AS$

$etc...$

And we are in the last step, so we have to clean up the remaining rules that are not in CNF.

1.

$S_0 \rightarrow AU_1|SB|AS$

$S \rightarrow ASB|SB|AS$

$U_1 \rightarrow SB$

$etc...$

2.

$S_0 \rightarrow AU_1|SB|AS$

$S \rightarrow AU_2|SB|AS$

$U_1 \rightarrow SB$

$U_2 \rightarrow SB$

$etc...$

So my question is: Can't I simply put in the step 2. $S \rightarrow AU_1|SB|AS$ instead of creating the variable $U_2$?

1

There are 1 best solutions below

1
On

$U_1$ and $U_2$ could be obtained from completely different previous rules, so unless you specify how $U_1$ and $U_2$ are (potentially the same way) derived, this is perfectly fine for a minimally defined CFG.