387 views

The left-factoring of the given CFG is

• $S \rightarrow aBcD \mid aBD \mid daB \mid d$
• $B \rightarrow b$
• $D \rightarrow d$
1. $S \rightarrow aBB' \mid d$
$B' \rightarrow cD \mid D$
$B \rightarrow b$
$D \rightarrow d$
2. $S \rightarrow B'cD \mid B'D \mid d$
$B' \rightarrow aB$
$B \rightarrow b$
$D \rightarrow d$
3. $S \rightarrow B'cD \mid B'D \mid dB' \mid d$
$B' \rightarrow aB$
$B \rightarrow b$
$D \rightarrow d$
4. None of them

Left-Factoring : The process of conversion of the grammar with common prefixes into deterministic grammar is known as left factoring.
Syntax: if the CFG is of the form $A \rightarrow aA_1 \mid aA_2 \mid \dots aA_n$
Left factored grammar is
$A \rightarrow aA'$
$A' \rightarrow A_1 \mid A_2 \mid \dots A_n$
Left factored grammar for the given grammar is
$S \rightarrow aA' \mid dB'$
$A' \rightarrow BcD \mid BD$
$B' \rightarrow aB \mid \epsilon$
$B \rightarrow b$
$D \rightarrow d$

does left factored  only applied to starting symbol?
why not C

1 vote
1
550 views
1 vote