Espressioni regolari
Possiamo utilizzare le operazioni regolari (unione, concatenazione e star) per costruire espressioni
Il valore dell’espressione regolare è un linguaggio
Abbiamo visto che un automa a stati finiti è un modo per definire linguaggi regolari
Vedremo che una espressione regolare è un modo dichiarativo per descrivere un linguaggio regolare
Definizione induttiva
Base
- $a$ è un’espressione regolare per ogni $a\in \sum$
- $\epsilon$ è un’espressione regolare
- $\empty$ è un’espressione regolare
Passo
- se $R_1$ e $R_2$ sono espressioni regolari, allora $R_1 \cup R_2$ è un’espressione regolare
- se $R_1$ e $R_2$ sono espressioni regolari, allora $R_1 \circ R_2$ è un’espressione regolare
- se $R$ è un’espressione regolare, allora $R^*$ è un’espressione regolare
Dimostrare proprietà sulle espressioni regolari
La definizione induttiva suggerisce un metodo per dimostrare che una espressione regolare $R$ soddisfa una certa proprietà
(Base) Si dimostra che la proprietà è soddisfatta per i casi base:
- è soddisfatta per $R=a$, dove $a \in \sum$
- è soddisfatta per $R= \epsilon$
- è soddisfatta per $R=\empty$