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

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

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

S'-->SA

A'-->a

B-->b

The Gateway to Computer Science Excellence

+1 vote

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

0

Nitish, Typo! second line productions are for A, not for A'.

secondly A->b is missing, added due to null- productions removal.

secondly A->b is missing, added due to null- productions removal.

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?

S0->S

+

Original Productions

and the we start conversion from cfg to cnf?

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- 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.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,648 questions

56,422 answers

195,196 comments

99,862 users