Конкатенация на регулярни езици

Нека имаме два регулярни езика L₁, L₂. Ще докажем, че тяхната конкатенация L = L₁ ∘ L₂ също е регулярен език.

Какво е конкатенация

Чрез конкатенация на двете думи „010“ и „1111“ се получава думата „0101111“. Чрез конкатенация на езици се получава нов език, който построяваме така, че всяка дума от единия език конкатенираме с всяка дума от другия език. Конкатенацията на две думи и на два езика ще означаваме с кръгче: ∘. Тогава можем да определим конкатенацията на езиците L₁ и L₂ така:

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

Идея на доказателството

Имаме два регулярни езика L₁, L₂ и два автомата, които приемат тези езици:

$$\begin{array}{rcl}{A}_1& =& ⟨Q_1,{\mathrm{\Sigma }}_1,{\delta }_1,q_0,F_1⟩\\ A_2& =& ⟨Q_2,{\mathrm{\Sigma }}_2,{\delta }_2,p_0,F_2⟩\end{array}$$

Построяваме недетерминиран автомат A = ⟨Q, Σ, δ, q, F⟩, който ще „съдържа в себе си“ двата автомата A₁ и A₂. Основната идея е да започнем да приемаме думата с автомата A₁ и когато автоматът A₁ стигне до крайно състояние, да опитаме да приемем останалата част от думата с автомата A₂. Ако и този автомат приема тази част от думата, тогава автоматът A приема думата.

Пример

Нека имаме този автомат A₁, който приема непразните думи, съставени само от нули, и думите, съставени от единица, след която следват само нули (1, 10, 100, …):

и нека имаме този автомат A₂, който приема думите, които завършват на 01:

Свързваме автоматите така, че от всички крайни състояния на автомата A₁ добавяме ε-преходи към началното състояние на автомата A₂ и след това правим от крайните състояния на A₁ обикновени състояния. Началното състояние на целия нов автомат ще е началното състояние на автомата A₁:

Как ще работи автоматът? Започваме да симулираме работата на автомата A₁. Ако преминем в бившето крайно състояние q₁ или q₂, знаем, че автоматът A₁ приема част от тази дума. За да е цялата дума част от езика L₁ ∘ L₂, останалата част от думата трябва да бъде приета още от втория автомат A₂ — затова от всички бивши крайни състояния водят ε-преходи към първоначалното начално състояние на автомата A₂.

За пример да вземем думата 0001. Тя принадлежи на конкатенацията на двата езика, защото думата може да се получи чрез конкатенация на думите 00 ∘ 01. Но също така може да се получи чрез конкатенация на думите 0 ∘ 001. В нашия автомат можем да симулираме и двата начина. Автоматът може да върви по този път:

$$q_0{\to }^0{q}_1{\to }^0{q}_1{\to }^{\epsilon }{p}_0{\to }^0{p}_1{\to }^1{p}_2$$

По този път автоматът първо би „приел“ частта от думата 00 и след това частта от думата 01. Или може да върви по този път:

$$q_0{\to }^0{q}_1{\to }^{\epsilon }{p}_0{\to }^0{p}_0{\to }^0{p}_1{\to }^1{p}_2$$

и автоматът би „приел“ първо частта от думата 0 и после частта от думата 001. И в двата случая, разбира се, стигаме до крайното състояние p₂.

Формален метод

Още веднъж: имаме два регулярни езика L₁, L₂ и два автомата, които приемат тези езици:

$$\begin{array}{rcl}{A}_1& =& ⟨Q_1,{\mathrm{\Sigma }}_1,{\delta }_1,q_0,F_1⟩\\ A_2& =& ⟨Q_2,{\mathrm{\Sigma }}_2,{\delta }_2,p_0,F_2⟩\end{array}$$

Построяваме недетерминиран автомат A = ⟨Q, Σ, δ, q, F⟩, за който е в сила:

• Q = Q₁ ∪ Q₂ (като предполагаме, че Q₁ ∩ Q₂ = ∅)
• Σ= Σ₁ ∪ Σ₂
• q = q₀
• F = F₂

Преходната функция δ съставяме постепенно:

$$\delta (q,a)=\{\begin{array}{lll}{\delta }_1(q,a)& \text{ако}& q\in Q_1\wedge q\notin F_1\\ {\delta }_1(q,a)& \text{ако}& q\in F_1\wedge a\ne \epsilon \\ {\delta }_1(q,a)\cup \left\{p_0\right\}& \text{ако}& q\in F_1\wedge a=\epsilon \\ {\delta }_2(q,a)& \text{ако}& q\in Q_2\end{array}$$

Източници

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