Vereniging van reguliere talen

Neem twee reguliere talen L₁, L₂. We bewijzen dat hun vereniging L = L₁ ∪ L₂ ook een reguliere taal is.

Werkwijze met een deterministische automaat

Idee van de werkwijze

We hebben twee reguliere talen L₁ en L₂ en willen bewijzen dat hun vereniging L₁ ∪ L₂ weer een reguliere taal is. Omdat L₁ en L₂ reguliere talen zijn, bestaan er eindige automaten A₁ en A₂ die de talen L₁ en L₂ accepteren, dus er geldt L(A₁) = L₁ en L(A₂) = L₂. We construeren vervolgens een eindige automaat A die de taal L₁ ∪ L₂ accepteert, waarmee we bewijzen dat de taal L₁ ∪ L₂ regulier is.

Hoe doen we dat? We hebben de eindige automaten A₁ en A₂ bij de hand, die de afzonderlijke talen accepteren. We kunnen zeggen dat een woord w tot de taal L₁ ∪ L₂ behoort dan en slechts dan als minstens een van de automaten A₁ of A₂ het accepteert.

De automaat A zou zo kunnen werken dat hij voor de invoer w de berekening van automaat A₁ voor invoer w simuleert. Als A₁ het woord w accepteert, accepteert A het woord w ook. Als A₁ het woord w verwerpt, probeert A nog de berekening van A₂ voor invoer w te simuleren. Als A₂ het woord w accepteert, accepteert ook A het woord w. Anders verwerpt hij het.

We moeten nog formaliseren wat het betekent dat de automaat A de berekening van een andere automaat “simuleert”.

Formalisering

We hebben twee reguliere talen L₁ en L₂ die door de eindige automaten

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

worden geaccepteerd. We construeren een eindige automaat A = ⟨Q, Σ, δ, q, F⟩ die de taal L = L₁ ∪ L₂ accepteert. We gebruiken het idee van het simuleren van twee automaten A₁, A₂. Stel dat de invoer het woord w = w₁w₂… w_n is en dat we nu tegelijk het verloop van de automaten A₁ en A₂ voor het woord w simuleren. De beginconfiguratie van automaat A₁ is ⟨q₁, w₁w₂… w_n⟩, de beginconfiguratie van A₂ is ⟨q₂, w₁w₂… w_n⟩. In elke automaat doen we nu een rekenstap, waarmee we in de configuraties ⟨δ₁(q₁, w₁), w₂… w_n⟩ en ⟨δ₂(q₂, w₁), w₂… w_n⟩ komen.

We zien dat deze configuraties alleen in de eerste component verschillen; de tweede — het nog niet gelezen deel van het woord — is altijd hetzelfde. Tijdens de simulatie hoeven we dus geen twee configuraties van twee automaten bij te houden, maar volstaat één configuratie van de vorm ⟨⟨q_i, q_j⟩, w_l… w_n⟩, waarbij q_i ∈ Q₁ en q_j ∈ Q₂. Met andere woorden: onze automaat A heeft de beginconfiguratie ⟨⟨q₁, q₂⟩, w⟩. Het eerste deel van het paar ⟨q₁, q₂⟩ is de toestand waarin automaat A₁ zich op dat moment bevindt en de tweede component is de huidige toestand van automaat A₂.

We kunnen dus opschrijven dat de verzameling toestanden van de automaat A gelijk is aan Q = Q₁ × Q₂. Dat is het cartesisch product van de toestanden van de twee vorige automaten. Het idee is verder dat automaat A de begintoestand ⟨q₁, q₂⟩ heeft en dat als automaat A₁ voor het symbool w₁ naar toestand q_i gaat en automaat A₂ voor het symbool w₁ naar toestand q_j gaat, automaat A voor het symbool w₁ naar toestand ⟨q_i, q_j⟩ gaat.

De overgangsfunctie δ schrijven we zo op (hier gaan we er al van uit dat we op dat moment in de toestanden q_i en q_j zitten):

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

We hoeven nog maar een paar details te regelen. Voor het alfabet geldt Σ= Σ₁ ∪ Σ₂. De begintoestand is q = ⟨q₁, q₂⟩. En de eindtoestanden zijn alle paren ⟨q_i, q_j⟩ zodat q_i ∈ F₁ of q_j ∈ F₂.

Illustratie van de werkwijze

Neem twee automaten. De eerste is automaat A₁, die alle woorden accepteert (inclusief het lege woord) waarin nullen en enen elkaar afwisselen, dus woorden van de vorm 01, 0101, 010101, …

De andere automaat A₂ accepteert woorden die minstens één nul bevatten:

De vereniging van deze talen bestaat uit de woorden die ofwel een nul bevatten ofwel van de vorm 01, 0101, … zijn. Nu construeren we een eindige automaat A = ⟨Q, Σ, δ, q, F⟩ die precies deze verenigde taal accepteert. Eerst laten we zien hoe de toestanden van deze nieuwe automaat A eruit komen te zien. Dat wordt het cartesisch product van de toestanden van de eerste en de tweede automaat:

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

Zo zien de zes toestanden van automaat A eruit, die de verenigde taal L(A₁) ∪ L(A₂) accepteert. In het diagram zouden ze er zo uitzien:

Schrik er niet van dat we toestanden hebben die uit paren toestanden bestaan — dat dient alleen om beter te zien wat er in de automaat eigenlijk gebeurt. De toestanden zouden gerust gewoon q₀, …, q₅ kunnen heten. De eindtoestanden zijn de toestanden die ofwel toestand q₀ ofwel p₁ bevatten, de eindtoestanden van de oorspronkelijke automaten. De begintoestand is ⟨q₀, p₀⟩.

Nu moeten we alle overgangen vinden. We maken zo'n 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}$

En we vullen de tabel stap voor stap in. Eerst bepalen we waarheen de overgang vanuit toestand ⟨q₀, p₀⟩ bij invoer 0 loopt. We bepalen waarheen de overgang vanuit toestand q₀ bij invoer 0 loopt in automaat A₁: die loopt naar toestand q₁. In automaat A₂ loopt de overgang vanuit p₀ bij nul naar toestand p₁. We schrijven in de tabel dus ⟨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}$

Bij invoer 1 krijgen we: voor automaat A₁ hebben we δ₁(q₀, 1) = q₂ en voor automaat A₂ hebben we δ₂(p₀, 1) = p₀. We krijgen dus toestand ⟨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}$

We vullen de rest van de tabel in:

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

En aan de hand van deze tabel tekenen we de rest van het diagram.

We kunnen uitproberen of de automaat werkt zoals het hoort. We proberen het woord 0100 te accepteren. De automaat doorloopt achtereenvolgens de toestanden

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

Omdat toestand ⟨q₂, p₁⟩ een eindtoestand is, accepteert automaat A het woord 0100. Hoe zou het aflopen als we het woord 0100 door de automaten A₁ en A₂ zouden laten accepteren? Automaat A₁ zou achtereenvolgens deze toestanden doorlopen:

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

De automaat eindigde in toestand q₂, die geen eindtoestand is, dus automaat A₁ zou dit woord niet accepteren. En automaat A₂?

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

Toestand p₁ is een eindtoestand, dus automaat A₂ zou het woord 0100 accepteren. Merk op dat de automaten A₁ en A₂ eindigden in de toestanden q₂ en p₁, wat overeenkomt met het feit dat automaat A eindigde in toestand ⟨q₂, p₁⟩.

Werkwijze met een niet-deterministische automaat

Voorbeeld

Dat de verzameling van de reguliere talen afgesloten is onder vereniging, kunnen we ook bewijzen door een niet-deterministische automaat te construeren, die veel eenvoudiger is.

We hebben dus twee reguliere talen L₁, L₂ en willen bewijzen dat hun vereniging L = L₁ ∪ L₂ ook een reguliere taal is. Omdat L₁, L₂ reguliere talen zijn, moeten er automaten A₁, A₂ bestaan die deze talen accepteren. Er geldt dus L(A₁) = L₁ en L(A₂) = L₂. Met deze automaten construeren we een automaat A die de taal L accepteert, dus L(A) = L.

Stel dat de eindige automaten A₁ en A₂ er zo uitzien:

Een automaat die de vereniging van beide talen accepteert, construeren we door een nieuwe begintoestand te maken en daaruit twee epsilonovergangen naar de oorspronkelijke begintoestanden te trekken. Dat is alles. De automaat zou er zo uitzien:

Formalisering

We hebben twee automaten A₁ = ⟨Q₁, Σ, δ₁, q₁, F₁⟩ en A₂ = ⟨Q₂, Σ, δ₂, q₂, F₂⟩. We construeren een automaat A = ⟨Q, Σ, δ, q₀, F⟩ die de vereniging accepteert van de talen die door de vorige automaten worden geaccepteerd, dus L(A) = L(A₁) ∪ L(A₂). Daarbij geldt:

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

En de overgangsfunctie δ definiëren we zo:

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

Bronnen

Hoofdstukken: Afgeslotenheid van reguliere talen, Vereniging van reguliere talen, Doorsnede van reguliere talen, Verschil van reguliere talen, Complement van een reguliere taal, Concatenatie van reguliere talen, Afsluiting van een reguliere taal

« Vorige: Afsluitingseigenschappen van reguliere talen

Volgende: Doorsnede van reguliere talen »