Intersezione di linguaggi regolari

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

Idea della dimostrazione

Abbiamo due linguaggi regolari L₁ e L₂ e vogliamo dimostrare che la loro intersezione 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.

Una parola appartiene all’intersezione dei linguaggi se appartiene a L₁ e allo stesso tempo a L₂. Quindi la parola deve essere accettata sia dall’automa A₁ sia dall’automa A₂. Usiamo esattamente la stessa idea dell’unione di linguaggi regolari, cambiando soltanto l’insieme degli stati finali.

Formalizzazione del procedimento

Abbiamo due automi,

$$\begin{array}{rcl}{A}_1& =& ⟨Q_1,{\mathrm{\Sigma }}_1,{\delta }_1,q_0,F_1⟩\\ A_2& =& ⟨Q_2,{\mathrm{\Sigma }}_2,{\delta }_2,p_0,F_2⟩\end{array}$$

Costruiamo l’automa A = ⟨Q, Σ, δ, q, F⟩ che accetta il linguaggio L(A₁) ∩ L(A₂). Si ha:

• Q = Q₁ × Q₂
• Σ= Σ₁ ∩ Σ₂
• q = ⟨q₀, p₀⟩
• F = F₁ × F₂

Per la funzione di transizione δ vale la relazione seguente:

$$\mathrm{\forall }q\in Q_1,p\in Q_2:\delta (⟨q,p⟩,a)=⟨{\delta }_1(q,a),{\delta }_2(p,a)⟩$$

Esempio

Consideriamo questo automa A₁, che accetta tutte le parole con un numero pari di 1:

e l’automa A₂, che accetta le parole con un numero dispari di 0:

Costruiamo l’automa che accetta l’intersezione di questi linguaggi. L’insieme degli stati ha la forma Q = Q₁ × Q₂, lo stato iniziale è ⟨q₀, p₀⟩ e gli stati finali sono F₁ × F₂:

Poi completiamo le transizioni ponendo δ(⟨q,p⟩, a) = ⟨δ₁(q, a), δ₂(p, a)⟩:

In questo automa, ad esempio, dallo stato ⟨q₀, p₀⟩ c’è una transizione con il simbolo 0 verso lo stato ⟨q₀,p₁⟩. Significa che l’automa A₁ ha, dallo stato q₀, una transizione con il simbolo 0 che torna in q₀, mentre l’automa A₂ con il simbolo 0 passa dallo stato p₀ allo stato p₁.

Possiamo mettere alla prova l’automa. Dovrebbe accettare parole come 110 o 00000 (contengono un numero pari di 1 e allo stesso tempo un numero dispari di 0), ma non dovrebbe accettare parole come 11, 111, 1010.

Fonti

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools