The Gateway to Computer Science Excellence

+2 votes

Consider the following context free grammar:

$S \rightarrow ASA | aB$

$A \rightarrow B | S$

$B \rightarrow b | \epsilon$

How many productions will be there in the modified grammar if we remove null-productions and unit-productions from this grammar?

My Solution:

**Step 1**: Remove epsilon transitions

Nullable variables = $ \big\{A,B\big\} $

Modified grammar after removal of null productions:

$S \rightarrow ASA | aB | a | AS | SA | S$

$A \rightarrow B | S $

$B \rightarrow b$

**Step 2**: Remove Unit Productions

$S \rightarrow ASA |aB |a | AS | SA | \mathbf{S}$

$A \rightarrow \mathbf {B} | \mathbf{S}$

$B \rightarrow b$

Modified grammar after the removal of the unit productions:

$S \rightarrow ASA |aB |a | AS | SA$

$A \rightarrow b | ASA |aB |a | AS | SA$

$B \rightarrow b$

I am getting 12 productions. can someone please confirm if it's correct?

0

srestha mam

If the qsn was about simplify the grammer, then Can I write A->ab instead of A->aB & remove the production B->b ???

In that case we'll have 11 productions.

please confirm this.

52,215 questions

60,013 answers

201,242 comments

94,700 users