Chomsky Normal Form (CNF)

Advertisement

Chomsky Normal Form (CNF)

It cannot contain the null, that CFG in which non-terminals belongs to two non-terminal. Or non-terminal belongs to only one terminal and non-terminal does not null, this is known as Chomsky Normal Form.

  • Non-terminal = two non-terminal
  • Non-terminal = only one terminal’
  • Non-terminal ≠ Null

For Example:

S→aSb│bSb│aa│bb│a│b

It is not CNF. Now we will convert it into Normal Form by applying this method.

A→a

B→b

C→AS

D→BS

The CNF will be in this form:

S→ASA│BSB│AA│BB│A│B

S→ASA│BSB│AA│BB│a│b

S→CA│DB│AA│BB│a│b

Algorithm for Conversion into CNF:

Step 1:

If the start symbol S occurs on some right side, create a new start symbol S’ and a new production S’→ S.

Step 2:

Removal of the Null Production.

Step 3:

Removal of the unit production.

Step 4:

Replace each production A → B1…Bn where n > 2 with A → B1C. Where C → B2 …Bn. Repeat this step for all productions having two or more symbols on the right side.

Advertisement

Step 5:

If the right side of any product is in the form A → aB. Where a is a terminal and A, B are non-terminal, then the production is replaced by A → XB and X → a. Repeat this step for every product which is in the form A → aB.

CFG Properties and Applications

Advertisement

Zitoc

We are a team of writers, researchers, and editors who are passionate about helping others live their best lives. We believe that life is a beautiful gift. We try to live our lives to the fullest and enjoy every moment. We are always learning and growing, and we cherish the relationships we have with our family and friends.