# FLC - lesson 03
##### Luca Oddone Breveglieri
###### 8 october 2015

## Regular Expressions

__Regular Languages__ are the simplest family of formal languages.  
Can be defined in different ways:
- algebrically
- through generating grammars
- through recognizer machines

__Regular Expression__ (*regexp*) is a string $r$ defined with the terminal alphabet $\Sigma$  
containing some *metasymbols*  
##### Possible cases:
$r,s,t$ are regexp
1. $r=\varnothing$
2. $r=a, \;\;a\in \Sigma$
3. $r=s\cup t\;\; \text{or}\;\; r=s|t$
4. $r=s.t\;\; \text{or}\;\; r=st$
5. $r=s^*$ <!--*-->
##### Precedence of operators
1. star *
2. concatenation .
3. union $\cup$ or |

A language is __regular__ if it is generated by a *regular expression*

regexp|language
---|---
$\varepsilon \;\text{or}\;\varnothing$|$\{\varepsilon\}$
$a\in\Sigma$|$\{a\}$
$s \cup t \; \text{or} \; s \mid t$ | $L_s \cup L_t$
$s.t \; \text{or} \; st$ | $L_s.L_t$
$s^*$|${L_s}^*$

#####example
>The regexp $e$ that generates the language of integers, possibly signed  
$e={(+\cup - \cup\varepsilon)dd}^*$ $L_e=\{+,-,\varepsilon\}\{d\}\{d\}^*$

__Family of regular languages__ or __REG__:  
Is the collection of all regular languages.

__Family of finite languages__ or __FIN__:  
Is the collection of all languages of finite cardinality.