Обединение на регулярни езици

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

Начин с детерминиран автомат

Идея на метода

Имаме два регулярни езика L₁ и L₂ и искаме да докажем, че тяхното обединение L₁ ∪ L₂ е отново регулярен език. Тъй като L₁ и L₂ са регулярни езици, съществуват крайни автомати A₁ и A₂, които приемат езиците L₁ и L₂, т.е. L(A₁) = L₁ и L(A₂) = L₂. Ние ще построим краен автомат A, който ще приема езика L₁ ∪ L₂, с което ще докажем, че езикът L₁ ∪ L₂ е регулярен.

Как ще го направим? Под ръка имаме крайните автомати A₁ и A₂, които приемат отделните езици. Можем да кажем, че думата w принадлежи на езика L₁ ∪ L₂ тогава и само тогава, когато я приеме поне един от автоматите A₁ или A₂.

Автоматът A би могъл да работи така, че за вход w да симулира изчислението на автомата A₁ за вход w. Ако A₁ приеме думата w, тогава и A приема думата w. Ако A₁ отхвърли думата w, тогава A още ще се опита да симулира изчислението на A₂ за вход w. Ако A₂ приеме думата w, тогава и A приема думата w. В противен случай я отхвърля.

Остава да формализираме какво означава, че автоматът A „симулира“ изчислението на друг автомат.

Формализация

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

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

Построяваме краен автомат A = ⟨Q, Σ, δ, q, F⟩, който ще приема езика L = L₁ ∪ L₂. Ще използваме идеята за симулиране на два автомата A₁, A₂. Нека си представим, че на входа имаме думата w = w₁w₂… w_n и сега ще симулираме едновременно хода на автоматите A₁ и A₂ за думата w. Началната конфигурация на автомата A₁ е ⟨q₁, w₁w₂… w_n⟩, началната конфигурация на A₂ е ⟨q₂, w₁w₂… w_n⟩. Във всеки автомат сега извършваме стъпка на изчислението, с което стигаме до конфигурациите ⟨δ₁(q₁, w₁), w₂… w_n⟩ и ⟨δ₂(q₂, w₁), w₂… w_n⟩.

Виждаме, че тези конфигурации се различават само в първата компонента, втората — непрочетената част от думата — е винаги една и съща. По време на симулацията следователно не е нужно да поддържаме две конфигурации на два автомата, достатъчна ни е една конфигурация от вида ⟨⟨q_i, q_j⟩, w_l… w_n⟩, където q_i ∈ Q₁ и q_j ∈ Q₂. С други думи, автоматът A, който построяваме, ще има начална конфигурация ⟨⟨q₁, q₂⟩, w⟩. Първата част на двойката ⟨q₁, q₂⟩ представлява състоянието, в което се намира в момента автоматът A₁, а втората компонента представлява текущото състояние на автомата A₂.

Можем така да запишем, че автоматът A, който построяваме, ще има множество от състояния, равно на Q = Q₁ × Q₂. Това ще е декартовото произведение на състоянията на предишните два автомата. Следващата идея е такава: автоматът A ще има начално състояние ⟨q₁, q₂⟩ и ако автоматът A₁ за символа w₁ премине в състоянието q_i, а автоматът A₂ за символа w₁ премине в състоянието q_j, то автоматът A за символа w₁ ще премине в състоянието ⟨q_i, q_j⟩.

Преходната функция δ записваме така (тук вече предполагаме, че в момента сме в състоянията q_i и q_j):

$$\delta (⟨q_i,q_j⟩,w)=⟨{\delta }_1(q_i,w),{\delta }_2(q_j,w)⟩$$

Остава да уредим само дреболиите. За азбуката е в сила Σ= Σ₁ ∪ Σ₂. Началното състояние е равно на q = ⟨q₁, q₂⟩. А крайни състояния са всички двойки ⟨q_i, q_j⟩, такива че q_i ∈ F₁ или q_j ∈ F₂.

Илюстрация на метода

Нека имаме два автомата. Първият е автоматът A₁, който приема всички думи (включително празната дума), в които се редуват нули и единици, т.е. думи от вида 01, 0101, 010101, …

Другият автомат A₂ приема думите, които съдържат поне една нула:

Обединението на тези езици са думите, които или съдържат нула, или са от вида 01, 0101, … Сега ще построим краен автомат A = ⟨Q, Σ, δ, q, F⟩, който ще приема точно този обединен език. Първо ще покажем как ще изглеждат състоянията на този нов автомат A. Това ще е декартовото произведение на състоянията на първия и втория автомат:

$$Q=Q_1\times Q_2=\{⟨q_0,p_0⟩,⟨q_0,p_1⟩,⟨q_1,p_0⟩,⟨q_1,p_1⟩,⟨q_2,p_0⟩,⟨q_2,p_1⟩\}$$

Така изглеждат шестте състояния на автомата A, който приема обединения език L(A₁) ∪ L(A₂). В диаграмата биха изглеждали така:

Не се стряскай, че имаме състояния, които се състоят от двойки състояния — това служи само за по-добра ориентация в това, което всъщност се случва в автомата. Състоянията спокойно биха могли да се казват по обичайния начин q₀, …, q₅. Крайни са онези състояния, които съдържат или състоянието q₀, или p₁, а те са крайните състояния на първоначалните автомати. Началното състояние е ⟨q₀, p₀⟩.

Сега трябва да намерим всички преходи. Съставяме такава таблица:

$$\begin{array}{ccc}& 0& 1\\ ⟨q_0,p_0⟩\\ ⟨q_0,p_1⟩\\ ⟨q_1,p_0⟩\\ ⟨q_1,p_1⟩\\ ⟨q_2,p_0⟩\\ ⟨q_2,p_1⟩\end{array}$$

И постепенно ще попълваме таблицата. Първо откриваме къде ще води преходът от състоянието ⟨q₀, p₀⟩ при вход 0. Откриваме къде води преходът от състоянието q₀ при вход 0 в автомата A₁: той води към състоянието q₁. В автомата A₂ преходът от p₀ при нула води към състоянието p₁. Така в таблицата записваме ⟨q₁, p₁⟩:

$$\begin{array}{ccc}& 0& 1\\ ⟨q_0,p_0⟩& ⟨q_1,p_1⟩\\ ⟨q_0,p_1⟩\\ ⟨q_1,p_0⟩\\ ⟨q_1,p_1⟩\\ ⟨q_2,p_0⟩\\ ⟨q_2,p_1⟩\end{array}$$

При вход 1 получаваме: за автомата A₁ имаме δ₁(q₀, 1) = q₂, а за автомата A₂ имаме δ₂(p₀, 1) = p₀. Така получаваме състоянието ⟨q₂, p₀⟩.

$$\begin{array}{ccc}& 0& 1\\ ⟨q_0,p_0⟩& ⟨q_1,p_1⟩& ⟨q_2,p_0⟩\\ ⟨q_0,p_1⟩\\ ⟨q_1,p_0⟩\\ ⟨q_1,p_1⟩\\ ⟨q_2,p_0⟩\\ ⟨q_2,p_1⟩\end{array}$$

Дописваме останалата част от таблицата:

$$\begin{array}{ccc}& 0& 1\\ ⟨q_0,p_0⟩& ⟨q_1,p_1⟩& ⟨q_2,p_0⟩\\ ⟨q_0,p_1⟩& ⟨q_1,p_1⟩& ⟨q_2,p_1⟩\\ ⟨q_1,p_0⟩& ⟨q_2,p_1⟩& ⟨q_0,p_0⟩\\ ⟨q_1,p_1⟩& ⟨q_2,p_1⟩& ⟨q_0,p_1⟩\\ ⟨q_2,p_0⟩& ⟨q_2,p_1⟩& ⟨q_2,p_0⟩\\ ⟨q_2,p_1⟩& ⟨q_2,p_1⟩& ⟨q_2,p_1⟩\end{array}$$

И по тази таблица вече само дорисуваме останалата част от диаграмата.

Можем да проверим, че автоматът работи както трябва. Ще опитаме да приемем думата 0100. Автоматът последователно минава през състоянията

$$⟨q_0,p_0⟩,⟨q_1,p_1⟩,⟨q_0,p_1⟩,⟨q_1,p_1⟩,⟨q_2,p_1⟩$$

Тъй като състоянието ⟨q₂, p₁⟩ е крайно, автоматът A приема думата 0100. Какво би станало, ако опитаме да приемем думата 0100 с автоматите A₁ и A₂? Автоматът A₁ би минал последователно през тези състояния:

$$q_0,q_1,q_0,q_1,q_2$$

Автоматът свършва в състоянието q₂, което не е крайно, така че автоматът A₁ не би приел тази дума. А автоматът A₂?

$$p_0,p_1,p_1,p_1,p_1$$

Състоянието p₁ е крайно, така че автоматът A₂ би приел думата 0100. Забележи, че автоматите A₁ и A₂ свършиха в състоянията q₂ и p₁, което е в съответствие с това, че автоматът A свърши в състоянието ⟨q₂, p₁⟩.

Начин с недетерминиран автомат

Пример

Че множеството на регулярните езици е затворено относно обединението, можем да докажем и чрез построяване на недетерминиран автомат, който ще е много по-прост.

Имаме два регулярни езика L₁, L₂ и искаме да докажем, че тяхното обединение L = L₁ ∪ L₂ също е регулярен език. Тъй като L₁, L₂ са регулярни езици, трябва да съществуват автомати A₁, A₂, които приемат тези езици. Т.е. L(A₁) = L₁ и L(A₂) = L₂. С помощта на тези автомати ще построим автомата A, който ще приема езика L, т.е. L(A) = L.

Да допуснем, че крайните автомати A₁ и A₂ изглеждат така:

и

Автомата, който би приемал обединението на двата езика, бихме построили така, че да създадем ново начално състояние и от това състояние да прокараме два ε-прехода към първоначалните начални състояния. Това е всичко. Автоматът би изглеждал така:

Формализация

Имаме два автомата A₁ = ⟨Q₁, Σ, δ₁, q₁, F₁⟩ и A₂ = ⟨Q₂, Σ, δ₂, q₂, F₂⟩. Построяваме автомата A = ⟨Q, Σ, δ, q₀, F⟩, който ще приема обединението на езиците, приемани от предишните автомати, т.е. L(A) = L(A₁) ∪ L(A₂). При това е в сила:

• Q = Q₁ ∪ Q₂ ∪ {q₀}
• F = F₁ ∪ F₂

А преходната функция δ определяме така:

$$\delta (q,a)=\{\begin{array}{lll}{\delta }_1(q,a)& \text{ако}& q\in Q_1\\ {\delta }_2(q,a)& \text{ако}& q\in Q_2\\ \{q_1,q_2\}& \text{ако}& q=q_0\wedge a=\epsilon \\ \mathrm{\varnothing }& \text{ако}& q=q_0\wedge a\ne \epsilon \end{array}$$

Източници

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