Operazioni regolari

<aside> 💡 Siano $A$ e $B$ linguaggi, definiamo le operazioni regolari unione, concatenazione e star (o kleene star) come segue:

• unione: $A \cup B = \{x | x \in A \lor x \in B\}$
• concatenazione: $A \circ B = \{xy| x \in A \land y \in B\}$
• star: $A^* = \{x_1..x_k|k \geq 0$ e ogni $x_i \in A\}$ </aside>

Chiusura

Una collezione $S$ di oggetti è chiusa per un’operazione $f$ se applicando $f$ a membri di $S$, $f$ restituisce un oggetto ancora in $S$

Dato un DFA $M_1$ che riconosce il linguaggio $L$, possiamo costruire un DFA $M_2$ che riconosce il linguaggio complemento $L' = \overline{L}$

• gli stati accettanti in $M_1$ diventano non accettanti in $M_2$
• gli stati non accettanti in $M_1$ diventano accettanti in $M_2$

Quindi $L$ regolare $\Rightarrow$ $\overline{L}$ regolare

Teorema

<aside> 💡 L’insieme dei linguaggi regolari è chiuso per l’operazione di complemento

</aside>

• Dimostrazione

Teorema

<aside> 💡 La classe dei linguaggi regolari è chiusa per l’operazione di unione Cioè se $L_1$ e $L_2$ sono linguaggi regolari, allora lo è anche $L_1 \cup L_2$

</aside>

• Dimostrazione (idea)

Teorema

<aside> 💡 La classe dei linguaggi regolari è chiusa per l’operazione di intersezione Cioè se $L_1$ e $L_2$ sono linguaggi regolari, allora lo è anche $L_1 \cap L_2$

</aside>

• Dimostrazione (idea)

Teorema

<aside> 💡 La classe dei linguaggi regolari è chiusa per l’operazione di concatenazione Cioè se $L_1$ e $L_2$ sono linguaggi regolari, allora lo è anche $L_1 \circ L_2$

</aside>