Zwykłe zamknięcie języka
Kapitoly: Zamykanie języków regularnych, Unifikacja, Dostęp, Różnica, Uzupełnienie, Konkatenacja, Wnioski
Mamy regularny język L. Udowodnimy, że domknięcie L jest ponownie regularnym językiem.
Co to jest domknięcie języka?
Domknięcie języka L oznaczamy jako $L^\ast$. Domknięcie zawiera wszystkie słowa, które można połączyć przez konkatenację skończonej liczby słów z języka L. Zamknię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 również puste słowo, tj. ε.
Procedura formalna
Będziemy postępować w bardzo podobny sposób, jak w przypadku konkatenacji języków. Tylko zamiast łączyć dwa różne automaty, łączymy jeden automat - prowadząc w ten sposób przejścia epsilon ze stanów końcowych automatu do stanu początkowego automatu. Zamknięcie musi jednak zawierać również puste słowo. Jak to zorganizować? Możemy uczynić stan początkowy stanem końcowym. Wtedy taki automat zaakceptowałby puste słowo, ale mógłby też zaakceptować inne słowo. Dlatego zamiast tego tworzymy nowy stan początkowy i z tego nowego stanu początkowego prowadzimy przejście epsilon do oryginalnego stanu początkowego.
Mamy regularny język L1 i automat, który akceptuje ten język:
\begin{eqnarray} A_1&=&\left<Q_1, \Sigma_1, \delta_1, q_0, F_1\right> \end{eqnarray}
Konstruujemy niedeterministyczny automat $A=\left<Q, \Sigma, \delta, q_s, F\right>$, dla którego zachodzi następująca zależność:
- Q = Q1 ∪ {qs}
- $\Sigma = \Sigma_1$
- F = F1 ∪ {qs}
Definiujemy funkcję przejścia δ w następujący sposób:
$$ \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
Rozważmy automat A1, który akceptuje słowa 00 lub 11:
Domknięciem języka L(A1) jest zatem język wszystkich słów składających się z par 00 i 11, na przykład 0000, 110011, 11110000 itd. Skonstruowalibyśmy automat, który akceptuje to domknięcie, tworząc nowy stan początkowy qs z przejściem epsilon do poprzedniego stanu początkowego q0 i dodając przejścia epsilon ze stanów q3 i q4 do stanu q0:
Możemy zweryfikować, że ten automat rzeczywiście akceptuje słowa 0000, 110011, 11110000, ale nie zaakceptuje, powiedzmy, 1010.