Domknięcie Kleene’ego języka regularnego
Kapitoly: Domkniętość języków regularnych, Suma, Przecięcie, Różnica, Dopełnienie, Konkatenacja, Domknięcie Kleene’ego
Mamy język regularny L. Udowodnimy, że domknięcie Kleene’ego języka L jest znowu językiem regularnym.
Co to jest domknięcie języka
Domknięcie (Kleene’ego) języka L oznaczamy $L^\ast$. Domknięcie zawiera wszystkie słowa, które da się złożyć przez konkatenację skończonej liczby słów z języka L. Domknięcie możemy zdefiniować jako:
$$ L^\ast = \left\{a_1\circ a_2 \circ \dots \circ a_n ,|, a_i \in L, n \in \mathbb{N}_0 \right\}, $$
gdzie $\circ$ oznacza operację konkatenacji. Domknięcie zawiera też słowo puste, czyli ε.
Konstrukcja formalna
Będziemy postępować bardzo podobnie jak w przypadku konkatenacji języków. Tyle że zamiast łączyć dwa różne automaty, połączymy jeden automat sam ze sobą – ze stanów akceptujących automatu poprowadzimy epsilon-przejścia do stanu początkowego automatu. Domknięcie musi jednak zawierać też słowo puste. Jak to załatwić? Moglibyśmy ze stanu początkowego zrobić stan akceptujący. Wtedy taki automat zaakceptowałby słowo puste, ale mógłby zaakceptować też jakieś inne słowo, które do domknięcia nie należy. Dlatego zamiast tego utworzymy nowy stan początkowy i z tego nowego stanu początkowego poprowadzimy epsilon-przejście do pierwotnego stanu początkowego.
Mamy język regularny L1 i automat, który ten język akceptuje:
\begin{eqnarray} A_1&=&\left<Q_1, \Sigma_1, \delta_1, q_0, F_1\right> \end{eqnarray}
Zbudujemy automat niedeterministyczny $A=\left<Q, \Sigma, \delta, q_s, F\right>$, dla którego zachodzi:
- Q = Q1 ∪ {qs}
- $\Sigma = \Sigma_1$
- F = F1 ∪ {qs}
Funkcję przejścia δ definiujemy tak:
$$ \delta(q, a) = \begin{cases} \delta_1(q, a)&\mbox{jeśli}&q\in Q_1 \wedge q\notin F_1\\ \delta_1(q, a)&\mbox{jeśli}&q\in F_1 \wedge a\ne \epsilon\\ \delta_1(q, a)\cup\left\{q_0\right\}&\mbox{jeśli}&q\in F_1 \wedge a= \epsilon\\ \left\{q_0\right\}&\mbox{jeśli}&q=q_s \wedge a= \epsilon\\ \emptyset&\mbox{jeśli}&q=q_s \wedge a\ne \epsilon\\ \end{cases} $$
Przykład
Weźmy taki automat A1, który akceptuje słowa 00 i 11:
Domknięciem języka L(A1) jest więc język wszystkich słów, które składają się z par 00 i 11, na przykład 0000, 110011, 11110000 itp. Automat, który akceptowałby to domknięcie, zbudowalibyśmy tak, że utworzylibyśmy nowy stan początkowy qs z epsilon-przejściem do byłego stanu początkowego q0 i dodalibyśmy epsilon-przejścia ze stanów q3 i q4 do stanu q0:
Możemy sprawdzić, że ten automat naprawdę akceptuje słowa 0000, 110011, 11110000, ale nie zaakceptuje na przykład słowa 1010.