CODEWITHSUNDEEP
context-free-grammarchomsky-normal-form
user4088686
user4088686

Reputation:

How to use the 1st step in Chomsky Normal Form

I'm confused on when to use the 1st step in CNF conversion.

1st Step: ensure s does not appear on rhs, add new S0 if necessary and copy all rules of S

It is not clear to me what the above statement means. I dont know when to create S0. Some CFG doesnt start with S0 and some starts with S0.

A little help here bros.

Upvotes: 1

Views: 223

Answers (1)

user3125280
user3125280

Reputation: 2829

The point is to avoid having the start symbol appear on the rhs i.e. as the result of a production. Therefore, you create a distinct symbol that becomes the one and only start symbol.

What are some of the examples of CFG that seem incorrect to you? They may not start with so, but the symbol they do start with should not appear as the result of a production.

Upvotes: 1

Related Questions