Afsluiting van een reguliere taal

We hebben een reguliere taal L. We bewijzen dat de afsluiting van de taal L weer een reguliere taal is.

Wat is de afsluiting van een taal

De afsluiting van een taal L noteren we als L^∗. De afsluiting bevat alle woorden die zijn samen te stellen door een eindig aantal woorden uit de taal L te concateneren. We kunnen de afsluiting definiëren als:

$L^{*} = {a_{1} \circ a_{2} \circ \dots \circ a_{n} | a_{i} \in L, n \in N_{0}},$

waarbij ∘ de bewerking concatenatie aangeeft. De afsluiting bevat ook het lege woord, dus ϵ.

Formele werkwijze

We gaan vrijwel op dezelfde manier te werk als bij de concatenatie van talen. Alleen verbinden we niet twee verschillende automaten, maar koppelen we één automaat aan zichzelf — vanuit de eindtoestanden van de automaat trekken we epsilonovergangen naar de begintoestand van de automaat. De afsluiting moet echter ook het lege woord bevatten. Hoe regelen we dat? We kunnen van de begintoestand een eindtoestand maken. Dan zou zo'n automaat het lege woord accepteren, maar misschien ook nog een ander woord. Daarom maken we in plaats daarvan een nieuwe begintoestand en trekken we vanuit die nieuwe begintoestand een epsilonovergang naar de oorspronkelijke begintoestand.

We hebben een reguliere taal L₁ en een automaat die deze taal accepteert:

$\begin{array}{rcl} A_{1} & = & ⟨ Q_{1}, Σ_{1}, δ_{1}, q_{0}, F_{1} ⟩ \end{array}$

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

Q = Q₁ ∪ {q_s}
Σ= Σ₁
F = F₁ ∪ {q_s}

De overgangsfunctie δ definiëren we als volgt:

$δ (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 {q_{0}} & als & q \in F_{1} \land a = ϵ \\ {q_{0}} & als & q = q_{s} \land a = ϵ \\ \emptyset & als & q = q_{s} \land a \neq ϵ \end{cases}$

Voorbeeld

Neem deze automaat A₁, die de woorden 00 of 11 accepteert:

De afsluiting van de taal L(A₁) is dus de taal van alle woorden die uit paren 00 en 11 bestaan, bijvoorbeeld 0000, 110011, 11110000 enzovoort. Een automaat die deze afsluiting zou accepteren, bouwen we door een nieuwe begintoestand q_s te maken met een epsilonovergang naar de voormalige begintoestand q₀ en door epsilonovergangen toe te voegen van de toestanden q₃ en q₄ naar toestand q₀:

We kunnen controleren dat deze automaat de woorden 0000, 110011, 11110000 inderdaad accepteert, maar bijvoorbeeld het woord 1010 niet.

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: Concatenatie van reguliere talen

Volgende: Reguliere expressies »