FLC - lesson 07

Luca Oddone Breveglieri

22 october 2015

Grammars pt.V

###Chomsky Normal Form

The production rules are only of two types

Binary rule $$A\rightarrow BC\;\text{where}\;B,C\in V$$
Terminal rule $$A\rightarrow \alpha\;\text{where}\;\alpha \in \Sigma$$

If the language contains the empty string, add the rule $$S\rightarrow\varepsilon$$

Syntax tree

Every internal node has arity 2
Every node that is parent of a leaf as arity 1

How to transform left recustion into right recursion

Construction of the non left-recursive form

Transformation of the immediate left recursion

Transformation ...