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

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

Теорема

Для любых обычных языков ${displaystyle L_ {1}}$ и ${displaystyle L_ {2}}$ , язык ${displaystyle L_ {1} чашка 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} чашка A_ {2})}

куда

{displaystyle Q = Q_ {1} чашка Q_ {2} чашка {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} и x = epsilon emptyset & {mbox {if}} & q = q_ {0} и xeq epsilon end {array}} ight.}

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

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

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

С ${displaystyle N_ {1}}$ принимает ${displaystyle x_ {1} x_ {2} cdots x_ {m}}$ , существуют ${displaystyle r_ {0}, r_ {1}, cdots r_ {m} в 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} дюйм 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})) Стрелка вправо r_ {m} в 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} в A_ {1} чашка A_ {2}, r_ { 0}, r_ {1}, cdots r_ {m} в 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 }} г_ {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} в A_ {1} чашка A_ {2}, r_ { 0}, r_ {1}, cdots r_ {m} в Q}

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

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

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

Теорема

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