Converting a grammar to Chomsky normal form Chomsky normal form

1 converting grammar chomsky normal form

1.1 start: eliminate start symbol right-hand sides
1.2 term: eliminate rules nonsolitary terminals
1.3 bin: eliminate right-hand sides more 2 nonterminals
1.4 del: eliminate ε-rules
1.5 unit: eliminate unit rules
1.6 order of transformations

converting grammar chomsky normal form

to convert grammar chomsky normal form, sequence of simple transformations applied in order; described in textbooks on automata theory. presentation here follows hopcroft, ullman (1979), adapted use transformation names lange, leiß (2009). each of following transformations establishes 1 of properties required chomsky normal form.

start: eliminate start symbol right-hand sides

introduce new start symbol s0, , new rule

s0 → s,

where s previous start symbol. doesn t change grammar s produced language, , s0 won t occur on rule s right-hand side.

term: eliminate rules nonsolitary terminals

to eliminate each rule

a → x1 ... ... xn

with terminal symbol being not symbol on right-hand side, introduce, every such terminal, new nonterminal symbol na, , new rule

na → a.

change every rule

a → x1 ... ... xn

to

a → x1 ... na ... xn.

if several terminal symbols occur on right-hand side, simultaneously replace each of them associated nonterminal symbol. doesn t change grammar s produced language.

bin: eliminate right-hand sides more 2 nonterminals

replace each rule

a → x1 x2 ... xn

with more 2 nonterminals x1,...,xn rules

a → x1 a1,
a1 → x2 a2,
... ,
an-2 → xn-1 xn,

where ai new nonterminal symbols. again, doesn t change grammar s produced language.

del: eliminate ε-rules

an ε-rule rule of form

a → ε,

where not s0, grammar s start symbol.

to eliminate rules of form, first determine set of nonterminals derive ε. hopcroft , ullman (1979) call such nonterminals nullable, , compute them follows:

if rule → ε exists, nullable.
if rule → x1 ... xn exists, , every single xi nullable, nullable, too.

obtain intermediate grammar replacing each rule

a → x1 ... xn

by versions nullable xi omitted. deleting in grammar each ε-rule, unless left-hand side start symbol, transformed grammar obtained.

for example, in following grammar, start symbol s0,

s0 → abb | c
b → aa | ac
c → b | c
a → | ε

the nonterminal a, , hence b, nullable, while neither c nor s0 is. hence following intermediate grammar obtained:

s0 → abb | abb | abb | abb   |   c
b → aa | aa | aa | aεa   |   ac | ac
c → b | c
a → | ε

in grammar, ε-rules have been inlined @ call site . in next step, can hence deleted, yielding grammar:

s0 → abb | ab | bb | b   |   c
b → aa |   |   ac | c
c → b | c
a → a

this grammar produces same language original example grammar, viz. {ab,aba,abaa,abab,abac,abb,abc,b,bab,bac,bb,bc,c}, apparently has no ε-rules.

unit: eliminate unit rules

a unit rule rule of form

a → b,

where a, b nonterminal symbols. remove it, each rule

b → x1 ... xn,

where x1 ... xn string of nonterminals , terminals, add rule

a → x1 ... xn

unless unit rule has been (or being) removed.

order of transformations

when choosing order in above transformations applied, has considered transformations may destroy result achieved other ones. example, start re-introduce unit rule if applied after unit. table shows orderings admitted.

moreover, worst-case bloat in grammar size depends on transformation order. using |g| denote size of original grammar g, size blow-up in worst case may range |g| 2, depending on transformation algorithm used. blow-up in grammar size depends on order between del , bin. may exponential when del done first, linear otherwise. unit can incur quadratic blow-up in size of grammar. orderings start,term,bin,del,unit , start,bin,del,unit,term lead least (i.e. quadratic) blow-up.

cite error: there <ref group=note> tags on page, references not show without {{reflist|group=note}} template (see page).