Removing epsilon-transitions from context-free grammar

366 Views Asked by At

I have a context-free grammar; I have to remove epsilon-transitions:

$S \to 0A0|0$

$A \to BC|2| CCC$

$B \to 1C | 3D | \epsilon$

$C \to AA3 | \epsilon$

$D \to AAB | 2$


By alghoritm , I create $N_{0}$ that will hold all nonterminals that contain $\epsilon$ and in the next steps I add nonterminals that have rule that contains only nonterminals from previous iteration of $N$ e.g.,

1) $N_{0} = \{\}$

2) $N_{1} = \{B,C\}$

3) $N_{2} = \{B,C,A\}$

4) $N_{3} = \{B,C,A,D,S\}$

Now I have to adjust rules. We can remove nonterminals in $N_{3}$ object from rules, thus we have to create all combinations without it, e.g.,

$S \to 0A0|00|0$

$A \to BC | B | C | CCC | CC$

$B \to 1C | 1 | 3D | 3$

$C \to AA3| A3 | 3$

$D \to AAB | AA | A | AB | B | 2$

We see that no nonterminal is useless, so is this the final context-free grammar? Or did I make mistakes somewhere?

Thanks for answers and help.

1

There are 1 best solutions below

0
On

In the first phase of the conversion I'm familiar with (e.g., Hopcroft and Ullman, Introduction to Automata Theory, Languages, and Computation), you collect what are known as nullable variables. These are the nonterminals that can produce the empty string. In the grammar you gave, $S$ is not one of those; $A$, $B$, $C$, and $D$ are.

In the second phase---as you say---you "adjust the rules." For each production that contains nullable variables in the right-hand side, and for each nonempry subset of those variables, add a production obtained by removing that subset from the right-hand side, unless removing the subset leaves the empty string. Apart from omitting $A \to 2$, your resulting grammar looks OK.