# FLC - lesson 04
##### Luca Oddone Breveglieri
###### 12 october 2015
## Free Grammars pt.I

### Grammars
Are meant to overcome the limits of regexp  
Are composed by:
- A __starting language__
- A __set of rules__ which can be applied a finite number of times

A language can be defined by rules that after multiple applications allow to generates all and only the phrases in the language  

##### example:
__Language__
$$L=\{uu^R|u\in \{a,b\}^*\}=\{\varepsilon,aa,bb,abba,baab,...,abbbba,...\}$$
__Grammar rules__
$\text{frase}\rightarrow \varepsilon$  - The empty string is a valid phrase
$\text{frase}\rightarrow a\;\text{frase}\;a$ - A phrase encloses in a, a it's a phrase
$\text{frase}\rightarrow b\;\text{frase}\;b$ - A phrase encloses in b, b it's a phrase
<!--*-->
__Derivation chain__
$$\text{frase}\Rightarrow a\;\text{frase}\;a$$
Lista, frase are __non-terminal__ symbols
##### example 2:
The metalanguage of regular expressions
__syntax__
$1.\;espr \rightarrow\emptyset$

#### Context-free Grammars
Is a generalization of regexp

###Reduction of the grammars