Operazioni su linguaggi

Tra due linguaggi $A$ e $B$ qualsiasi sono definite:

Unione: $A \cup B = {w ∣ w \in A \lor w \in B}$
Concatenazione: $A \circ B = {w_{1} w_{2} ∣ w_{1} \in A \land w_{2} \in B}$ , con $∣ A \circ B ∣ = ∣ A \times B ∣$
Star: $A^{*} = {w_{1} w_{2} \dots w_{k} ∣ k \geq 0 \land w_{i} \in A, \forall i = 1, ..., k}$ , che conterrà $ϵ$

Chiusure

La classe dei linguaggi regolari è chiusa rispetto alle precedenti operazioni, ovvero se $A$ e $B$ sono regolari allora è regolare anche il risultato delle operazioni su di essi.

Dati due linguaggi regolari $A$ e $B$ , la chiusura dell'unione si può dimostrare perchè: $\exists M_{1} = (Q_{1}, Σ_{1}, δ_{1}, q_{1}, F_{1}), M_{2} = (Q_{2}, Σ_{2}, δ_{2}, q_{2}, F_{2}) : L (M_{1}) = A \land L (M_{2}) = B ⇓ \exists M = (Q, Σ, δ, q_{0}, F) : L (M) = A \cup B$

Questo è possibile perchè $M_{1}$ e $M_{2}$ sono simulabili in parallelo, assumendo che $Σ = Σ_{1} = Σ_{2}$ :

$Q = Q_{1} \times Q_{2}$
$q_{0} = (q_{1}, q_{2})$ , composto dagli stati iniziali di $M_{1}$ e $M_{2}$
$F = {(r_{1}, r_{2}) \in Q ∣ r_{1} \in F_{1} \lor r_{2} \in F_{2}}$
$δ ((r_{1}, r_{2}), a) = (δ (r_{1}, a), δ (r_{2}, a)), \forall (r_{1}, r_{2}) \in Q, a \in Σ$

L'assunzione per cui $Σ = Σ_{1} = Σ_{2}$ non è limitante perchè basta aggiungere uno stato pozzo, per esempio

ha alfabeto ${a, b}$ , e si può trasformare in ${a, b, c}$ con:

Concatenazione

Se due linguaggi $A$ e $B$ sono regolari allora esistono gli NFA $N_{1}$ e $N_{2}$ che li rappresentano, e concatenandoli si crea l'NFA $N$ per cui $L (N) = A \circ B$ e si dimostra la chiusura della concatenazione:

Quindi, se $N_{1} = (Q_{1}, Σ_{1}, δ_{1}, q_{1}, F_{1})$ e $N_{2} = (Q_{2}, Σ_{2}, δ_{2}, q_{2}, F_{2})$ , allora $N = (Q, Σ, δ, q_{0}, F)$ è definito:

$Q = Q_{1} \cup Q_{2}$
$q_{0} = q_{1}$
$F = F_{2}$
$δ (q, a) = ⎩ ⎨ ⎧ δ_{1} (q, a) δ_{2} (q, a) δ_{1} (q, a) {q_{2}} \cup δ_{1} (q, a) se q \in Q_{1} ∖ F_{1} se q \in Q_{2} se q \in F_{1} \land a \neq = ϵ se q \in F_{1} \land a = ϵ$

Star

Come per la concatenazione, la chiusura di star rispetto ad $L (N) = A$ si dimostra costruendo un NFA $M$ :

Computer Science

Operazioni su linguaggi

Chiusure

Unione

Concatenazione

Star