Unione di linguaggi regolari

Siano L₁, L₂ due linguaggi regolari. Dimostreremo che anche la loro unione L = L₁ ∪ L₂ è un linguaggio regolare.

Procedimento con un automa deterministico

Idea del procedimento

Abbiamo due linguaggi regolari L₁ e L₂ e vogliamo dimostrare che la loro unione L₁ ∪ L₂ è ancora un linguaggio regolare. Poiché L₁ e L₂ sono regolari, esistono automi a stati finiti A₁ e A₂ che accettano i linguaggi L₁ e L₂, cioè L(A₁) = L₁ e L(A₂) = L₂. Costruiremo un automa a stati finiti A che accetta il linguaggio L₁ ∪ L₂, e così dimostreremo che L₁ ∪ L₂ è regolare.

Come procediamo? Abbiamo gli automi a stati finiti A₁ e A₂, che accettano i singoli linguaggi. Possiamo dire che la parola w appartiene al linguaggio L₁ ∪ L₂ se e solo se è accettata da almeno uno degli automi A₁ o A₂.

L’automa A potrebbe funzionare così: per l’ingresso w simula il calcolo dell’automa A₁ sull’ingresso w. Se A₁ accetta la parola w, allora la parola w è accettata anche da A. Se A₁ rifiuta la parola w, allora A prova a simulare il calcolo di A₂ sull’ingresso w. Se A₂ accetta la parola w, allora anche A accetta la parola w. Altrimenti la rifiuta.

Ci resta da formalizzare cosa significa che l’automa A «simula» il calcolo di un altro automa.

Formalizzazione

Abbiamo due linguaggi regolari L₁ e L₂, accettati dagli automi a stati finiti

$\begin{array}{rcl} A_{1} & = & ⟨ Q_{1}, Σ_{1}, δ_{1}, q_{1}, F_{1} ⟩ \\ A_{2} & = & ⟨ Q_{2}, Σ_{2}, δ_{2}, q_{2}, F_{2} ⟩ . \end{array}$

Costruiamo l’automa a stati finiti A = ⟨Q, Σ, δ, q, F⟩ che accetta il linguaggio L = L₁ ∪ L₂. Sfruttiamo l’idea di simulare due automi A₁, A₂. Immaginiamo di avere in ingresso la parola w = w₁w₂… w_n e di simulare contemporaneamente l’esecuzione degli automi A₁ e A₂ sulla parola w. La configurazione iniziale dell’automa A₁ è ⟨q₁, w₁w₂… w_n⟩, quella di A₂ è ⟨q₂, w₁w₂… w_n⟩. In ciascun automa eseguiamo ora un passo di calcolo e arriviamo alle configurazioni ⟨δ₁(q₁, w₁), w₂… w_n⟩ e ⟨δ₂(q₂, w₁), w₂… w_n⟩.

Vediamo che queste configurazioni differiscono solo nella prima componente, mentre la seconda – la parte non ancora letta della parola – è sempre la stessa. Durante la simulazione non serve quindi mantenere due configurazioni di due automi: ne basta una della forma ⟨⟨q_i, q_j⟩, w_l… w_n⟩, dove q_i ∈ Q₁ e q_j ∈ Q₂. In altre parole, l’automa A che stiamo costruendo avrà la configurazione iniziale ⟨⟨q₁, q₂⟩, w⟩. La prima parte della coppia ⟨q₁, q₂⟩ rappresenta lo stato in cui si trova al momento l’automa A₁ e la seconda componente rappresenta lo stato attuale dell’automa A₂.

Possiamo quindi scrivere che l’automa A avrà come insieme degli stati Q = Q₁ × Q₂. Sarà il prodotto cartesiano degli stati dei due automi precedenti. L’idea è che l’automa A abbia lo stato iniziale ⟨q₁, q₂⟩ e che, se l’automa A₁ con il simbolo w₁ passa nello stato q_i e l’automa A₂ con il simbolo w₁ passa nello stato q_j, allora l’automa A con il simbolo w₁ passa nello stato ⟨q_i, q_j⟩.

La funzione di transizione δ si scrive così (qui supponiamo di trovarci già negli stati q_i e q_j):

$δ (⟨ q_{i}, q_{j} ⟩, w) = ⟨ δ_{1} (q_{i}, w), δ_{2} (q_{j}, w) ⟩$

Restano solo alcuni dettagli. Per l’alfabeto vale Σ= Σ₁ ∪ Σ₂. Lo stato iniziale è q = ⟨q₁, q₂⟩. Gli stati finali sono tutte le coppie ⟨q_i, q_j⟩ tali che q_i ∈ F₁ oppure q_j ∈ F₂.

Illustrazione del procedimento

Consideriamo due automi. Il primo è l’automa A₁, che accetta tutte le parole (compresa la parola vuota) in cui si alternano zeri e uni, cioè le parole della forma 01, 0101, 010101, …

L’altro automa A₂ accetta le parole che contengono almeno uno zero:

L’unione di questi linguaggi è formata dalle parole che contengono uno zero oppure hanno la forma 01, 0101, … Costruiamo ora l’automa a stati finiti A = ⟨Q, Σ, δ, q, F⟩ che accetta proprio questo linguaggio unione. Per prima cosa vediamo come saranno fatti gli stati del nuovo automa A. Il loro insieme sarà il prodotto cartesiano degli stati del primo e del secondo automa:

$Q = Q_{1} \times Q_{2} = {⟨ q_{0}, p_{0} ⟩, ⟨ q_{0}, p_{1} ⟩, ⟨ q_{1}, p_{0} ⟩, ⟨ q_{1}, p_{1} ⟩, ⟨ q_{2}, p_{0} ⟩, ⟨ q_{2}, p_{1} ⟩}$

Questi sono i sei stati dell’automa A che accetta il linguaggio unione L(A₁) ∪ L(A₂). Nel diagramma sarebbero così:

Non spaventarti se ci sono stati formati da coppie di stati: serve solo a orientarsi meglio in ciò che accade nell’automa. Gli stati potrebbero tranquillamente chiamarsi in modo classico q₀, …, q₅. Gli stati finali sono quelli che contengono lo stato q₀ oppure p₁, che sono gli stati finali degli automi originali. Lo stato iniziale è ⟨q₀, p₀⟩.

Ora dobbiamo trovare tutte le transizioni. Scriviamo una tabella di questo tipo:

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ \end{array}$

e la completiamo a poco a poco. Per prima cosa vediamo dove porta la transizione dallo stato ⟨q₀, p₀⟩ con l’ingresso 0. Vediamo dove porta la transizione dallo stato q₀ con l’ingresso 0 nell’automa A₁: porta nello stato q₁. Nell’automa A₂ la transizione da p₀ con lo zero porta nello stato p₁. Quindi nella tabella scriviamo ⟨q₁, p₁⟩:

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ & ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ \end{array}$

Con l’ingresso 1 otteniamo: per l’automa A₁ abbiamo δ₁(q₀, 1) = q₂ e per l’automa A₂ abbiamo δ₂(p₀, 1) = p₀. Otteniamo così lo stato ⟨q₂, p₀⟩.

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ & ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ \end{array}$

Completiamo il resto della tabella:

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ & ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ & ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{0}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ \end{array}$

E in base a questa tabella non resta che disegnare il resto del diagramma.

Possiamo verificare che l’automa funziona come deve. Proviamo a dargli in ingresso la parola 0100. L’automa attraversa in successione gli stati

$⟨ q_{0}, p_{0} ⟩, ⟨ q_{1}, p_{1} ⟩, ⟨ q_{0}, p_{1} ⟩, ⟨ q_{1}, p_{1} ⟩, ⟨ q_{2}, p_{1} ⟩$

Poiché lo stato ⟨q₂, p₁⟩ è finale, l’automa A accetta la parola 0100. Come andrebbe se dessimo in ingresso la parola 0100 agli automi A₁ e A₂? L’automa A₁ attraverserebbe in successione questi stati:

$q_{0}, q_{1}, q_{0}, q_{1}, q_{2}$

L’automa è finito nello stato q₂, che non è finale, quindi A₁ non accetterebbe questa parola. E l’automa A₂?

$p_{0}, p_{1}, p_{1}, p_{1}, p_{1}$

Lo stato p₁ è finale, quindi l’automa A₂ accetterebbe la parola 0100. Osserva che gli automi A₁ e A₂ sono finiti negli stati q₂ e p₁, in accordo con il fatto che l’automa A è finito nello stato ⟨q₂, p₁⟩.

Procedimento con un automa non deterministico

Esempio

Il fatto che l’insieme dei linguaggi regolari sia chiuso rispetto all’unione si può dimostrare anche costruendo un automa non deterministico, che sarà molto più semplice.

Abbiamo quindi due linguaggi regolari L₁, L₂ e vogliamo dimostrare che la loro unione L = L₁ ∪ L₂ è anch’essa un linguaggio regolare. Poiché L₁, L₂ sono linguaggi regolari, devono esistere automi A₁, A₂ che accettano questi linguaggi. Cioè vale L(A₁) = L₁ e L(A₂) = L₂. Con questi automi costruiamo l’automa A che accetta il linguaggio L, cioè L(A) = L.

Supponiamo che gli automi a stati finiti A₁ e A₂ siano fatti così:

L’automa che accetta l’unione dei due linguaggi si costruisce creando un nuovo stato iniziale e facendo partire da questo stato due ε-transizioni verso gli stati iniziali originali. Tutto qui. L’automa sarebbe così:

Formalizzazione

Abbiamo due automi A₁ = ⟨Q₁, Σ, δ₁, q₁, F₁⟩ e A₂ = ⟨Q₂, Σ, δ₂, q₂, F₂⟩. Costruiamo l’automa A = ⟨Q, Σ, δ, q₀, F⟩ che accetta l’unione dei linguaggi accettati dagli automi precedenti, cioè L(A) = L(A₁) ∪ L(A₂). Inoltre vale:

Q = Q₁ ∪ Q₂ ∪ {q₀}
F = F₁ ∪ F₂

E la funzione di transizione δ si definisce così:

$δ (q, a) = {\begin{cases} δ_{1} (q, a) & se & q \in Q_{1} \\ δ_{2} (q, a) & se & q \in Q_{2} \\ {q_{1}, q_{2}} & se & q = q_{0} \land a = ε \\ \emptyset & se & q = q_{0} \land a \neq ε \end{cases}$

Fonti

Capitoli: Chiusura dei linguaggi regolari, Unione di linguaggi regolari, Intersezione di linguaggi regolari, Differenza di linguaggi regolari, Complemento di un linguaggio regolare, Concatenazione di linguaggi regolari, Chiusura di Kleene di un linguaggio regolare

« Precedente: Proprietà di chiusura dei linguaggi regolari

Successivo: Intersezione di linguaggi regolari »