Konkatenacja języków regularnych

Weźmy dwa języki regularne L₁, L₂. Udowodnimy, że ich konkatenacja (złączenie) $L = L_1 \circ L_2$ też jest językiem regularnym.

Co to jest konkatenacja

Konkatenacją dwóch słów „010” i „1111” jest słowo „0101111”. Konkatenacją języków jest więc nowy język, który budujemy tak, że każde słowo z jednego języka łączymy (sklejamy) z każdym słowem z drugiego języka. Konkatenację dwóch słów i dwóch języków będziemy oznaczać kółkiem: $\circ$. Wtedy możemy zdefiniować konkatenację języków L₁ i L₂ tak:

$$ L_1 \circ L_2 = \left\{a\circ b,|, a\in L_1, b \in L_2\right\} $$

Idea dowodu

Mamy dwa języki regularne L₁, L₂ i dwa automaty, które te języki akceptują:

\begin{eqnarray} A_1&=&\left<Q_1, \Sigma_1, \delta_1, q_0, F_1\right>\\ A_2&=&\left<Q_2, \Sigma_2, \delta_2, p_0, F_2\right> \end{eqnarray}

Zbudujemy automat niedeterministyczny $A=\left<Q, \Sigma, \delta, q, F\right>$, który będzie „zawierał w sobie” oba automaty A₁ i A₂. Główna idea jest taka, że zaczniemy wczytywać słowo automatem A₁, a kiedy automat A₁ dojdzie do stanu akceptującego, pozostałą część słowa spróbujemy jeszcze zaakceptować automatem A₂. Jeśli także ten automat zaakceptuje tę część słowa, to automat A słowo akceptuje.

Przykład

Weźmy taki automat A₁, który akceptuje niepuste słowa złożone z samych zer oraz słowa złożone z jedynki, po której następują same zera (1, 10, 100, …):

oraz taki automat A₂, który akceptuje słowa kończące się na 01:

Automaty połączymy tak, że ze wszystkich stanów akceptujących automatu A₁ dodamy epsilon-przejścia do stanu początkowego automatu A₂, a następnie ze stanów akceptujących A₁ zrobimy zwykłe stany. Stanem początkowym całego nowego automatu będzie stan początkowy automatu A₁:

Jak będzie działał automat? Zaczniemy symulować działanie automatu A₁. Jeśli przejdziemy do byłego stanu akceptującego q₁ albo q₂, wiemy, że automat A₁ akceptuje część tego słowa. Żeby całe słowo należało do języka $L_1\circ L_2$, pozostałą część słowa musi jeszcze zaakceptować drugi automat A₂ – dlatego ze wszystkich byłych stanów akceptujących prowadzą epsilon-przejścia do pierwotnego stanu początkowego automatu A₂.

Weźmy na przykład słowo 0001. Należy ono do konkatenacji obu języków, bo słowo może powstać jako konkatenacja słów $00 \circ 01$. Ale równie dobrze może powstać jako konkatenacja słów $0\circ001$. W naszym automacie możemy zasymulować oba sposoby. Automat może pójść taką drogą:

$$ q_0 \rightarrow^0 q_1 \rightarrow^0 q_1 \rightarrow^{\varepsilon} p_0 \rightarrow^0 p_1 \rightarrow^1 p_2 $$

Tą drogą automat najpierw „zaakceptowałby” część słowa 00, a potem część słowa 01. Albo może pójść taką drogą:

$$ q_0 \rightarrow^0 q_1 \rightarrow^{\varepsilon} p_0 \rightarrow^0 p_0 \rightarrow^0 p_1 \rightarrow^1 p_2 $$

i wtedy automat najpierw „zaakceptowałby” część słowa 0, a potem część słowa 001. W obu przypadkach oczywiście dojdziemy do stanu akceptującego p₂.

Konstrukcja formalna

Jeszcze raz: mamy dwa języki regularne L₁, L₂ i dwa automaty, które te języki akceptują:

\begin{eqnarray} A_1&=&\left<Q_1, \Sigma_1, \delta_1, q_0, F_1\right>\\ A_2&=&\left<Q_2, \Sigma_2, \delta_2, p_0, F_2\right> \end{eqnarray}

Zbudujemy automat niedeterministyczny $A=\left<Q, \Sigma, \delta, q, F\right>$, dla którego zachodzi:

• Q = Q₁ ∪ Q₂ (zakładamy przy tym, że Q₁ ∩ Q₂ = ∅)
• $\Sigma = \Sigma_1 \cup \Sigma_2$
• q = q₀
• F = F₂

Funkcję przejścia δ zbudujemy po kolei:

$$ \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\varepsilon\\ \delta_1(q,a)\cup\left\{p_0\right\}&\mbox{jeśli}&q\in F_1\wedge a=\varepsilon\\ \delta_2(q,a)&\mbox{jeśli}&q\in Q_2 \end{cases} $$

Źródła

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools