Forening af regulære sprog

Vi har to regulære sprog L₁, L₂. Vi viser, at deres forening L = L₁ ∪ L₂ også er et regulært sprog.

Fremgangsmåde med en deterministisk automat

Idéen bag fremgangsmåden

Vi har to regulære sprog L₁ og L₂ og vil vise, at deres forening 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.

Hvordan gør vi det? Vi har de endelige automater A₁ og A₂, som accepterer de enkelte sprog. Vi kan sige, at ordet w hører til sproget L₁ ∪ L₂, netop hvis mindst én af automaterne A₁ eller A₂ accepterer det.

Automaten A kunne fungere sådan, at den for inputtet w simulerer automatens A₁ beregning for inputtet w. Hvis A₁ accepterer ordet w, accepterer A også ordet w. Hvis A₁ afviser ordet w, forsøger A derefter at simulere A₂'s beregning for inputtet w. Hvis A₂ accepterer ordet w, accepterer A også ordet w. I modsat fald afviser den.

Tilbage er at formalisere, hvad det betyder, at automaten A »simulerer« en anden automats beregning.

Formalisering

Vi har to regulære sprog L₁ og L₂, som accepteres af de endelige automater

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

Vi konstruerer en endelig automat A = ⟨Q, Σ, δ, q, F⟩, som vil acceptere sproget L = L₁ ∪ L₂. Vi udnytter idéen om at simulere to automater A₁, A₂. Forestil dig, at vi har inputordet w = w₁w₂… w_n, og at vi nu samtidig simulerer forløbet af automaterne A₁ og A₂ for ordet w. Startkonfigurationen for automaten A₁ er ⟨q₁, w₁w₂… w_n⟩, startkonfigurationen for A₂ er ⟨q₂, w₁w₂… w_n⟩. I hver automat udfører vi nu et beregningstrin, hvorved vi kommer til konfigurationerne ⟨δ₁(q₁, w₁), w₂… w_n⟩ og ⟨δ₂(q₂, w₁), w₂… w_n⟩.

Vi ser, at disse konfigurationer kun adskiller sig i første komponent, mens den anden — den endnu ikke læste del af ordet — altid er den samme. Under simulationen behøver vi derfor ikke at holde styr på to konfigurationer for to automater, men én konfiguration af formen ⟨⟨q_i, q_j⟩, w_l… w_n⟩ er nok, hvor q_i ∈ Q₁ og q_j ∈ Q₂. Med andre ord får den automat A, vi konstruerer, startkonfigurationen ⟨⟨q₁, q₂⟩, w⟩. Første del af parret ⟨q₁, q₂⟩ er den tilstand, som automaten A₁ aktuelt befinder sig i, og anden komponent er automatens A₂ aktuelle tilstand.

Vi kan altså skrive, at den automat A, vi konstruerer, har tilstandsmængden Q = Q₁ × Q₂. Det er det kartesiske produkt af tilstandene fra de to foregående automater. Den følgende idé er, at automaten A har starttilstanden ⟨q₁, q₂⟩, og hvis automaten A₁ for symbolet w₁ går over til tilstanden q_i, og automaten A₂ for symbolet w₁ går over til tilstanden q_j, så går automaten A for symbolet w₁ over til tilstanden ⟨q_i, q_j⟩.

Overgangsfunktionen δ skriver vi således (her antager vi allerede, at vi aktuelt er i tilstandene q_i og q_j):

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

Nu mangler kun detaljerne. For alfabetet gælder Σ= Σ₁ ∪ Σ₂. Starttilstanden er q = ⟨q₁, q₂⟩. Og accepttilstandene er alle par ⟨q_i, q_j⟩ sådan, at enten q_i ∈ F₁ eller q_j ∈ F₂.

Illustration af fremgangsmåden

Vi har to automater. Den første er automaten A₁, som accepterer alle ord (inklusive det tomme ord), hvor nuller og enere afløser hinanden, dvs. ord af formen 01, 0101, 010101, …

Den næste automat A₂ accepterer ord, der indeholder mindst ét nul:

Foreningen af disse sprog er ord, der enten indeholder et nul eller er af formen 01, 0101, … Nu konstruerer vi en endelig automat A = ⟨Q, Σ, δ, q, F⟩, som netop accepterer dette forenede sprog. Først viser vi, hvordan tilstandene i denne nye automat A kommer til at se ud. Det bliver det kartesiske produkt af tilstandene i den første og den anden automat:

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

Sådan ser de seks tilstande ud i automaten A, som accepterer det forenede sprog L(A₁) ∪ L(A₂). I diagrammet ville de se sådan ud:

Du skal ikke blive forskrækket over, at vi har tilstande, der består af par af tilstande — det tjener blot til bedre overblik over, hvad der egentlig sker i automaten. Tilstandene kunne sagtens hedde klassisk q₀, …, q₅. Accepttilstandene er de tilstande, der indeholder enten tilstanden q₀ eller p₁, som er accepttilstande i de oprindelige automater. Starttilstanden er ⟨q₀, p₀⟩.

Nu skal vi finde alle overgange. Vi opstiller en sådan tabel:

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

Og udfylder efterhånden tabellen. Først finder vi ud af, hvor overgangen fra tilstanden ⟨q₀, p₀⟩ fører hen ved inputtet 0. Vi finder ud af, hvor overgangen fra tilstanden q₀ fører hen ved inputtet 0 i automaten A₁: den fører til tilstanden q₁. I automaten A₂ fører overgangen fra p₀ ved nul til tilstanden p₁. Så i tabellen skriver vi ⟨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}$

Ved inputtet 1 får vi: for automaten A₁ har vi δ₁(q₀, 1) = q₂, og for automaten A₂ har vi δ₂(p₀, 1) = p₀. Vi får dermed tilstanden ⟨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}$

Vi udfylder resten af tabellen:

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

Og ud fra denne tabel tegner vi blot resten af diagrammet.

Vi kan prøve, om automaten fungerer, som den skal. Vi forsøger at acceptere ordet 0100. Automaten gennemløber efterhånden tilstandene

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

Da tilstanden ⟨q₂, p₁⟩ er en accepttilstand, accepterer automaten A ordet 0100. Hvordan ville det gå, hvis vi forsøgte at lade automaterne A₁ og A₂ acceptere ordet 0100? Automaten A₁ ville efterhånden gennemløbe disse tilstande:

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

Automaten endte i tilstanden q₂, som ikke er en accepttilstand, så automaten A₁ ville ikke acceptere dette ord. Hvad med automaten A₂?

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

Tilstanden p₁ er en accepttilstand, så automaten A₂ ville acceptere ordet 0100. Læg mærke til, at automaterne A₁ og A₂ endte i tilstandene q₂ og p₁, hvilket stemmer overens med, at automaten A endte i tilstanden ⟨q₂, p₁⟩.

Fremgangsmåde med en ikke-deterministisk automat

Eksempel

At mængden af regulære sprog er lukket under forening kan vi også vise ved at konstruere en ikke-deterministisk automat, som bliver meget enklere.

Vi har altså to regulære sprog L₁, L₂ og vil vise, at deres forening L = L₁ ∪ L₂ også er et regulært sprog. Da L₁, L₂ er regulære sprog, må der findes automater A₁, A₂, som accepterer disse sprog. Dvs. der gælder, at L(A₁) = L₁ og L(A₂) = L₂. Ved hjælp af disse automater konstruerer vi en automat A, som vil acceptere sproget L, dvs. L(A) = L.

Lad os antage, at de endelige automater A₁ og A₂ ser sådan ud:

Den automat, der ville acceptere foreningen af begge sprog, konstruerer vi ved at oprette en ny starttilstand og fra denne tilstand føre to epsilon-overgange til de oprindelige starttilstande. Det er alt. Automaten ville se sådan ud:

Formalisering

Vi har to automater A₁ = ⟨Q₁, Σ, δ₁, q₁, F₁⟩ og A₂ = ⟨Q₂, Σ, δ₂, q₂, F₂⟩. Vi konstruerer en automat A = ⟨Q, Σ, δ, q₀, F⟩, som vil acceptere foreningen af de sprog, der accepteres af de foregående automater, dvs. L(A) = L(A₁) ∪ L(A₂). Her gælder:

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

Og overgangsfunktionen δ definerer vi således:

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

Kilder

Kapitler: Lukkethed af regulære sprog, Forening af regulære sprog, Fællesmængde af regulære sprog, Differens af regulære sprog, Komplement af et regulært sprog, Konkatenering af regulære sprog, Kleene-stjerne af et regulært sprog

« Forrige: Lukkethedsegenskaber for regulære sprog

Næste: Fællesmængde af regulære sprog »