Союз двух обычных языков - Union of two regular languages

В формальный язык теория, и в частности теория недетерминированные конечные автоматы, известно, что союз двух обычных языков это обычный язык. В этой статье приводится доказательство этого утверждения.

Теорема

Для любых обычных языков ${displaystyle L_{1}}$ и ${displaystyle L_{2}}$, язык ${displaystyle L_{1}cup L_{2}}$ регулярно.

Доказательство

С ${displaystyle L_{1}}$ и ${displaystyle L_{2}}$ регулярны, существуют NFAs ${displaystyle N_{1}, N_{2}}$ которые признают ${displaystyle L_{1}}$ и ${displaystyle L_{2}}$.

Позволять

${displaystyle N_{1}=(Q_{1}, Sigma , T_{1}, q_{1}, A_{1})}$

${displaystyle N_{2}=(Q_{2}, Sigma , T_{2}, q_{2}, A_{2})}$^{[требуется разъяснение ]}

Построить

${displaystyle N=(Q, Sigma , T, q_{0}, A_{1}cup A_{2})}$

куда

${displaystyle Q=Q_{1}cup Q_{2}cup {q_{0}}}$

${displaystyle T(q,x)=left{{egin{array}{lll}T_{1}(q,x)&{mbox{if}}&qin Q_{1}T_{2}(q,x)&{mbox{if}}&qin Q_{2}{q_{1},q_{2}}&{mbox{if}}&q=q_{0} and x=epsilon emptyset &{mbox{if}}&q=q_{0} and xeq epsilon end{array}}ight.}$

В дальнейшем мы будем использовать ${displaystyle p{stackrel {x,T}{ightarrow }}q}$ обозначать ${displaystyle qin E(T(p,x))}$^{[требуется разъяснение ]}

Позволять ${displaystyle w}$ быть строкой из ${displaystyle L_{1}cup L_{2}}$. Не теряя общий смысл предполагать ${displaystyle win L_{1}}$.

Позволять ${displaystyle w=x_{1}x_{2}cdots x_{m}}$ куда ${displaystyle mgeq 0,x_{i}in Sigma }$

С ${displaystyle N_{1}}$ принимает ${displaystyle x_{1}x_{2}cdots x_{m}}$, существуют ${displaystyle r_{0},r_{1},cdots r_{m}in Q_{1}}$ такой, что^{[требуется разъяснение ]}

${displaystyle q_{1}{stackrel {epsilon ,T_{1}}{ightarrow }}r_{0}{stackrel {x_{1},T_{1}}{ightarrow }}r_{1}{stackrel {x_{2},T_{1}}{ightarrow }}r_{2}cdots r_{m-1}{stackrel {x_{m},T_{1}}{ightarrow }}r_{m},r_{m}in A_{1}}$

С ${displaystyle T_{1}(q,x)=T(q,x) forall qin Q_{1}forall xin Sigma }$

${displaystyle r_{0}in E(T_{1}(q_{1},epsilon ))Rightarrow r_{0}in E(T(q_{1},epsilon ))}$

${displaystyle r_{1}in E(T_{1}(r_{0},x_{1}))Rightarrow r_{1}in E(T(r_{0},x_{1}))}$

${displaystyle vdots }$

${displaystyle r_{m}in E(T_{1}(r_{m-1},x_{m}))Rightarrow r_{m}in E(T(r_{m-1},x_{m}))}$

Поэтому мы можем заменить ${displaystyle T}$ за ${displaystyle T_{1}}$ и перепишите указанный выше путь как

${displaystyle q_{1}{stackrel {epsilon ,T}{ightarrow }}r_{0}{stackrel {x_{1},T}{ightarrow }}r_{1}{stackrel {x_{2},T}{ightarrow }}r_{2}cdots r_{m-1}{stackrel {x_{m},T}{ightarrow }}r_{m},r_{m}in A_{1}cup A_{2},r_{0},r_{1},cdots r_{m}in Q}$

Более того,

${displaystyle {egin{array}{lcl}T(q_{0},epsilon )={q_{1},q_{2}}&Rightarrow &q_{1}in T(q_{0},epsilon )\&Rightarrow &q_{1}in E(T(q_{0},epsilon ))\&Rightarrow &q_{0}{stackrel {epsilon ,T}{ightarrow }}q_{1}end{array}}}$

и

${displaystyle q_{0}{stackrel {epsilon ,T}{ightarrow }}q_{1}{stackrel {epsilon ,T}{ightarrow }}r_{0}Rightarrow q_{0}{stackrel {epsilon ,T}{ightarrow }}r_{0}}$

Указанный выше путь можно переписать как

${displaystyle q_{0}{stackrel {epsilon ,T}{ightarrow }}r_{0}{stackrel {x_{1},T}{ightarrow }}r_{1}{stackrel {x_{2},T}{ightarrow }}r_{2}cdots r_{m-1}{stackrel {x_{m},T}{ightarrow }}r_{m},r_{m}in A_{1}cup A_{2},r_{0},r_{1},cdots r_{m}in Q}$

Следовательно, ${displaystyle N}$ принимает ${displaystyle x_{1}x_{2}cdots x_{m}}$ и доказательство завершено.^{[требуется разъяснение ]}

Примечание: Из этого математического доказательства извлечена идея создания машины для распознавания ${displaystyle L_{1}cup L_{2}}$ состоит в том, чтобы создать начальное состояние и связать его с начальными состояниями ${displaystyle L_{1}}$ и ${displaystyle L_{2}}$ с помощью ${displaystyle epsilon }$ стрелки.

Рекомендации

• Майкл Сипсер, Введение в теорию вычислений ISBN  0-534-94728-X. (См. Теорему 1.22, раздел 1.2, стр. 59.)