Fællesmængde af regulære sprog

Vi har to regulære sprog L₁, L₂. Vi viser, at deres fællesmængde L = L₁ ∩ L₂ også er et regulært sprog.

Idéen bag beviset

Vi har to regulære sprog L₁ og L₂ og vil vise, at deres fællesmængde L₁ ∩ L₂ igen er et regulært sprog. Da L₁ og L₂ er regulære sprog, findes der endelige automater A₁ og A₂, som accepterer sprogene L₁ og L₂, dvs. der gælder L(A₁) = L₁ og L(A₂) = L₂. Vi konstruerer nu en endelig automat A, som vil acceptere sproget L₁ ∩ L₂, og dermed viser vi, at sproget L₁ ∩ L₂ er regulært.

Et ord hører til fællesmængden af sprog, hvis det hører til både sproget L₁ og L₂. Ordet skal altså accepteres af både automaten A₁ og automaten A₂. Vi bruger nøjagtig den samme idé som ved forening af regulære sprog, vi ændrer blot mængden af accepttilstande.

Formalisering af fremgangsmåden

Vi har to automater,

$$\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}$$

Vi konstruerer en automat A = ⟨Q, Σ, δ, q, F⟩, som accepterer sproget L(A₁) ∩ L(A₂). Der gælder, at

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

For overgangsfunktionen δ gælder følgende sammenhæng:

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

Eksempel

Vi ser på denne automat A₁, som accepterer alle ord, der indeholder et lige antal 1'ere:

og automaten A₂, som accepterer ord, der indeholder et ulige antal 0'er:

Vi konstruerer en automat, som accepterer fællesmængden af disse sprog. Tilstandsmængden i denne automat har formen Q = Q₁ × Q₂, starttilstanden er tilstanden ⟨q₀, p₀⟩, og accepttilstandene er F₁ × F₂:

Derefter tegner vi overgangene, så δ(⟨q,p⟩, a) = ⟨δ₁(q, a), δ₂(p, a)⟩:

I denne automat er der for eksempel fra tilstanden ⟨q₀, p₀⟩ en overgang for symbolet 0 til tilstanden ⟨q₀,p₁⟩. Det betyder, at automaten A₁ har en overgang fra tilstanden q₀ for symbolet 0 tilbage til tilstanden q₀. Automaten A₂ har til gengæld for symbolet 0 en overgang fra tilstanden p₀ til tilstanden p₁.

Vi kan prøve automaten af. Den skal acceptere ord som 110 eller 00000 (de indeholder et lige antal 1'ere og samtidig et ulige antal 0'er), men den skal ikke acceptere ord som 11, 111, 1010.

Kilder

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