Spojení dvou běžných jazyků - Union of two regular languages

v formální jazyk teorie, a zejména teorie nedeterministické konečné automaty, je známo, že spojení dvou běžných jazyků je běžný jazyk. Tento článek poskytuje důkaz tohoto prohlášení.

Teorém

Pro všechny běžné jazyky ${displaystyle L_ {1}}$ a ${displaystyle L_ {2}}$, Jazyk ${displaystyle L_ {1} šálek L_ {2}}$ je pravidelný.

Důkaz

Od té doby ${displaystyle L_ {1}}$ a ${displaystyle L_ {2}}$ jsou pravidelné, existují NFA ${displaystyle N_ {1}, N_ {2}}$ které uznávají ${displaystyle L_ {1}}$ a ${displaystyle L_ {2}}$.

Nechat

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

${displaystyle N_ {2} = (Q_ {2}, Sigma, T_ {2}, q_ {2}, A_ {2})}$^{[je zapotřebí objasnění ]}

Postavit

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

kde

${displaystyle Q = Q_ {1} šálek Q_ {2} šálek {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} a x = epsilon emptyset & {mbox {if}} & q = q_ {0} a xeq epsilon end {array}} ight.}$

V následujícím textu použijeme ${displaystyle p {stackrel {x, T} {ightarrow}} q}$ naznačit ${displaystyle qin E (T (p, x))}$^{[je zapotřebí objasnění ]}

Nechat ${displaystyle w}$ být řetězec z ${displaystyle L_ {1} šálek L_ {2}}$. Bez ztráty obecnosti převzít ${displaystyle win L_ {1}}$.

Nechat ${displaystyle w = x_ {1} x_ {2} cdots x_ {m}}$ kde ${displaystyle mgeq 0, x_ {i} v Sigmě}$

Od té doby ${displaystyle N_ {1}}$ přijímá ${displaystyle x_ {1} x_ {2} cdots x_ {m}}$, existují ${displaystyle r_ {0}, r_ {1}, cdots r_ {m} v Q_ {1}}$ takhle^{[je zapotřebí objasnění ]}

${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} v A_ {1}}$

Od té doby ${displaystyle T_ {1} (q, x) = T (q, x) pro všechny qin Q_ {1} pro všechny xin Sigma}$

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

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

${displaystyle vdots}$

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

Můžeme tedy nahradit ${displaystyle T}$ pro ${displaystyle T_ {1}}$ a přepsat výše uvedenou cestu jako

${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} v A_ {1} poháru A_ {2}, r_ { 0}, r_ {1}, cdots r_ {m} v Q}$

Dále

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

a

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

Výše uvedená cesta může být přepsána jako

${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} v A_ {1} poháru A_ {2}, r_ { 0}, r_ {1}, cdots r_ {m} v Q}$

Proto, ${displaystyle N}$ přijímá ${displaystyle x_ {1} x_ {2} cdots x_ {m}}$ a důkaz je kompletní.^{[je zapotřebí objasnění ]}

Poznámka: Myšlenka vycházející z tohoto matematického důkazu pro konstrukci stroje k rozpoznání ${displaystyle L_ {1} šálek L_ {2}}$ je vytvořit počáteční stav a připojit ho k počátečním stavům ${displaystyle L_ {1}}$ a ${displaystyle L_ {2}}$ použitím ${displaystyle epsilon}$ šipky.

Reference

• Michael Sipser, Úvod do teorie výpočtu ISBN  0-534-94728-X. (Viz. Věta 1.22, část 1.2, str. 59.)