The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
1.1k views

Convert the following context free grammar into Chomsky Normal Form:

$S \rightarrow ASA | aB$

$A \rightarrow B | S$

$B \rightarrow b |  \epsilon$

Does the appearance of starting symbol S at RHS impacts the conversion from CFG to CNF?

in Theory of Computation by Boss (43.1k points) | 1.1k views
0
grammer in CNF will be,

S-->AS/ SA/ AS'/ A'B/ a

A-->AS'/ A'B/ AS/ SA/ a/ b

S'-->SA

A'-->a

B-->b
0
Nitish, Typo! second line productions are for A, not for A'.

secondly A->b is missing, added due to null- productions removal.
0
yes, sorry.......accidently!!
0
@nitish my doubt was if starting variable S appears at RHS in the original Grammar, do we need to add a temp variable? such as
S0->S
+
Original Productions

and the we start conversion from cfg to cnf?
0
@manu00x

no need for that..
0

@nitis

see the following screenshot taken from the book "Introduction to theory of computation" by Michael Sipser.

Please log in or register to answer this question.

Related questions

0 votes
1 answer
1
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,376 questions
55,836 answers
192,559 comments
91,336 users