The Gateway to Computer Science Excellence

0 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?

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.4k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.7k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,654 questions

56,166 answers

193,872 comments

94,261 users