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?

in Theory of Computation by Boss (43.3k points)
edited by | 355 views
getting same.
12 correct

Please log in or register to answer this question.

Related questions

+2 votes
4 answers
asked Jan 11, 2017 in Theory of Computation by KISHALAY DAS Active (4.9k points) | 911 views
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,654 questions
56,166 answers
94,261 users