• English only

# Lab for Automated Reasoning and Analysis LARA

## Transforming a Grammar to Chomsky Form

We show how to make a grammar:

• without unproductive symbols
• without unreachable symbols
• -free (no non-start nullable symbols)
• without single productions X::=Y (X,Y non-terminals)
• without productions of arity more than two
• with terminals occurring alone on right-hand side

### Elimination of Non-Productive Non-Terminals

Non-terminal is non-productive if it cannot generate any string of terminals

• if X::=w and w has only terminals, then X is productive
• if X:=p and p has only productive symbols, then X is productive

Start from empty set, apply these rules to compute productive symbols

• remaining symbols are non-productive
• delete them and all rules that contain them

### Elimination of Unreachable Non-Terminals

Non-terminal is unreachable if no derivation from start symbol contains it

• S is reachable
• if X is reachable and X::=p, then every symbol in p is reachable

Start from empty set, apply these rules to compute productive symbols

• remaining symbols are non-productive
• delete them and all rules that contain them

### Making Non-Terminals Non-Nullable

A grammar where is -free if

• no-non terminal is nullable, or
• only S is nullable and S does not appear on right-hand side

First, compute nullable (see Lecture 03)

Then, for each production

create all productions of form

where

• is (as before), or,
• is nullable and is empty string (so it disappears)

Remove all right-hand sides that are “”

If S is nullable, introduce new initial symbol S’ and add

### Eliminating Single Productions

Construct a directed graph of non-terminals between X,Y such that is production

Compute as the transitive closure of this graph

If X Y and Y ::= p is a rule, then add rule

X ::= p

Then remove single productions.

becomes

### Making Terminals Alone on Right-Hand Side

Just introduce a fresh non-terminal for terminal t

Use on RHS instead of t