polimd/Formal Languages and Compilers/lesson_03.md

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

6. star *

7. concatenation .

8. 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.