# 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__
1. Transformation of the immediate left recursion

### Transformation ...