Applied Course | Mock GATE | Test 1 | Question: 60

Question

The left-factoring of the given CFG is

• $S \rightarrow aBcD \mid aBD \mid daB \mid d$
• $B \rightarrow b$
• $D \rightarrow d$

• A. $S \rightarrow aBB' \mid d$
  $B' \rightarrow cD \mid D$
  $B \rightarrow b$
  $D \rightarrow d$
• B. $S \rightarrow B'cD \mid B'D \mid d$
  $B' \rightarrow aB$
  $B \rightarrow b$
  $D \rightarrow d$
• C. $S \rightarrow B'cD \mid B'D \mid dB' \mid d$
  $B' \rightarrow aB$
  $B \rightarrow b$
  $D \rightarrow d$
• D. None of them

Answer 1

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$

Comments

does left factored  only applied to starting symbol?

---

why not C