lesson_04.md 1.0 KB
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