Concatenazione di linguaggi regolari

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

Cos’è la concatenazione

Concatenando le due parole «010» e «1111» si ottiene la parola «0101111». La concatenazione di due linguaggi è quindi un nuovo linguaggio, che si costruisce concatenando ogni parola del primo linguaggio con ogni parola del secondo. La concatenazione di due parole e di due linguaggi si indica con un cerchietto: ∘. Possiamo allora definire la concatenazione dei linguaggi L₁ e L₂ così:

$L_{1} \circ L_{2} = {a \circ b ∣ a \in L_{1}, b \in L_{2}}$

Idea della dimostrazione

Abbiamo due linguaggi regolari L₁, L₂ e due automi che li accettano:

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

Costruiamo un automa non deterministico A = ⟨Q, Σ, δ, q, F⟩ che «contiene» entrambi gli automi A₁ e A₂. L’idea di base è di far leggere la parola all’automa A₁ e, quando A₁ arriva in uno stato finale, provare a far accettare la parte rimanente della parola all’automa A₂. Se anche questo automa accetta quella parte della parola, allora l’automa A accetta la parola.

Esempio

Consideriamo questo automa A₁, che accetta le parole non vuote formate solo da zeri e le parole formate da un 1 seguito solo da zeri (1, 10, 100, …):

e inoltre questo automa A₂, che accetta le parole che terminano con 01:

Colleghiamo gli automi aggiungendo ε-transizioni da tutti gli stati finali dell’automa A₁ allo stato iniziale dell’automa A₂, poi trasformiamo gli stati finali di A₁ in stati non finali. Lo stato iniziale del nuovo automa sarà lo stato iniziale di A₁:

Come funziona l’automa? Cominciamo simulando il funzionamento dell’automa A₁. Se arriviamo in un ex stato finale q₁ o q₂, sappiamo che l’automa A₁ accetta una parte di questa parola. Perché l’intera parola appartenga al linguaggio L₁ ∘ L₂, la parte rimanente deve essere accettata dal secondo automa A₂: per questo da tutti gli ex stati finali partono ε-transizioni verso lo stato iniziale originario dell’automa A₂.

Prendiamo ad esempio la parola 0001. Appartiene alla concatenazione dei due linguaggi, perché si può ottenere concatenando le parole 00 ∘ 01. Ma si può ottenere anche come 0 ∘ 001. Nel nostro automa possiamo simulare entrambi i procedimenti. L’automa può seguire questo percorso:

$q_{0} \to^{0} q_{1} \to^{0} q_{1} \to^{ε} p_{0} \to^{0} p_{1} \to^{1} p_{2}$

In questo percorso l’automa prima «accetta» la parte di parola 00 e poi la parte 01. Oppure può seguire questo percorso:

$q_{0} \to^{0} q_{1} \to^{ε} p_{0} \to^{0} p_{0} \to^{0} p_{1} \to^{1} p_{2}$

e così l’automa prima «accetta» la parte di parola 0 e poi la parte 001. In entrambi i casi arriviamo naturalmente nello stato finale p₂.

Procedimento formale

Ancora una volta: abbiamo due linguaggi regolari L₁, L₂ e due automi che li accettano:

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

Costruiamo un automa non deterministico A = ⟨Q, Σ, δ, q, F⟩ per cui vale:

Q = Q₁ ∪ Q₂ (supponiamo inoltre che Q₁ ∩ Q₂ = ∅)
Σ= Σ₁ ∪ Σ₂
q = q₀
F = F₂

La funzione di transizione δ si costruisce per casi:

$δ (q, a) = {\begin{cases} δ_{1} (q, a) & se & q \in Q_{1} \land q \notin F_{1} \\ δ_{1} (q, a) & se & q \in F_{1} \land a \neq ε \\ δ_{1} (q, a) \cup {p_{0}} & se & q \in F_{1} \land a = ε \\ δ_{2} (q, a) & se & q \in Q_{2} \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: Complemento di un linguaggio regolare

Successivo: Chiusura di Kleene di un linguaggio regolare »