Concatenatie van reguliere talen

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

Wat is concatenatie

Door de woorden “010” en “1111” te concateneren ontstaat het woord “0101111”. Door talen te concateneren ontstaat een nieuwe taal, die we construeren door elk woord uit de ene taal te concateneren met elk woord uit de andere taal. De concatenatie van twee woorden en van twee talen noteren we met een rondje: ∘. Dan kunnen we de concatenatie van de talen L₁ en L₂ als volgt definiëren:

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

Idee van het bewijs

We hebben twee reguliere talen L₁, L₂ en twee automaten die deze talen accepteren:

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

We construeren een niet-deterministische automaat A = ⟨Q, Σ, δ, q, F⟩ die beide automaten A₁ en A₂ “in zich bevat”. Het basisidee is dat we beginnen het woord te accepteren met automaat A₁ en dat, als automaat A₁ in een eindtoestand komt, we het resterende deel van het woord nog proberen te accepteren met automaat A₂. Als ook deze automaat dat deel van het woord accepteert, accepteert automaat A het woord.

Voorbeeld

Neem deze automaat A₁, die niet-lege woorden accepteert die alleen uit nullen bestaan en woorden die uit een één bestaan, gevolgd door alleen nullen (1, 10, 100, …):

en neem deze automaat A₂, die woorden accepteert die op 01 eindigen:

We koppelen de automaten door vanuit alle eindtoestanden van automaat A₁ epsilonovergangen naar de begintoestand van automaat A₂ toe te voegen en daarna van de eindtoestanden van A₁ gewone toestanden te maken. De begintoestand van de hele nieuwe automaat is de begintoestand van automaat A₁:

Hoe werkt de automaat? We beginnen de werking van automaat A₁ te simuleren. Als we in een voormalige eindtoestand q₁ of q₂ komen, weten we dat automaat A₁ een deel van dit woord accepteert. Om het hele woord tot de taal L₁ ∘ L₂ te laten behoren, moet het resterende deel van het woord nog door de tweede automaat A₂ worden geaccepteerd — daarom lopen vanuit alle voormalige eindtoestanden epsilonovergangen naar de oorspronkelijke begintoestand van automaat A₂.

Neem als voorbeeld het woord 0001. Dat behoort tot de concatenatie van beide talen, omdat het woord kan ontstaan door de woorden 00 ∘ 01 te concateneren. Maar het kan net zo goed ontstaan door de woorden 0 ∘ 001 te concateneren. In onze automaat kunnen we beide werkwijzen nabootsen. De automaat kan dit pad volgen:

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

Via dit pad zou de automaat eerst het deel 00 van het woord “accepteren” en daarna het deel 01. Of hij kan dit pad volgen:

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

en de automaat zou dan eerst het deel 0 van het woord “accepteren” en daarna het deel 001. In beide gevallen komen we natuurlijk in de eindtoestand p₂.

Formele werkwijze

Nog een keer: we hebben twee reguliere talen L₁, L₂ en twee automaten die deze talen accepteren:

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

We construeren een niet-deterministische automaat A = ⟨Q, Σ, δ, q, F⟩ waarvoor geldt:

Q = Q₁ ∪ Q₂ (tegelijk nemen we aan dat Q₁ ∩ Q₂ = ∅)
Σ= Σ₁ ∪ Σ₂
q = q₀
F = F₂

De overgangsfunctie δ bouwen we stap voor stap op:

$δ (q, a) = {\begin{cases} δ_{1} (q, a) & als & q \in Q_{1} \land q \notin F_{1} \\ δ_{1} (q, a) & als & q \in F_{1} \land a \neq ε \\ δ_{1} (q, a) \cup {p_{0}} & als & q \in F_{1} \land a = ε \\ δ_{2} (q, a) & als & q \in Q_{2} \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: Complement van een reguliere taal

Volgende: Afsluiting van een reguliere taal »