Teorema Myhill-Nerode

În teoria limbajelor formale, teorema Myhill-Nerode oferă o condiție necesară și suficientă pentru a stabili dacă un limbaj este regulat sau nu.

Conform teoremei Myhill-Nerode, fiecare limbă este regulată în alfabet $\Sigma$ ${\ displaystyle \ Sigma}$ $\ Sigma$ constă în unirea clasei de echivalență a unei relații drept-invariante a indicelui finit pe închiderea Kleene a $\Sigma$ ${\ displaystyle \ Sigma}$ $\ Sigma$ .

Definiții

Dat fiind un automat finit determinist $M=\left(Q,\Sigma ,\delta ,q_{0},F\right)$ ${\ displaystyle M = \ left (Q, \ Sigma, \ delta, q_ {0}, F \ right)}$ ${\ displaystyle M = \ left (Q, \ Sigma, \ delta, q_ {0}, F \ right)}$ se definește relația de echivalență

R_{M}:xR_{M}y\Longleftrightarrow {\hat {\delta }}\left(q_{0},x\right)={\hat {\delta }}\left(q_{0},y\right)

{\ displaystyle R_ {M}: xR_ {M} y \ Longleftrightarrow {\ hat {\ delta}} \ left (q_ {0}, x \ right) = {\ hat {\ delta}} \ left (q_ {0 }, y \ dreapta)}

{\ displaystyle R_ {M}: xR_ {M} y \ Longleftrightarrow {\ hat {\ delta}} \ left (q_ {0}, x \ right) = {\ hat {\ delta}} \ left (q_ {0 }, y \ dreapta)}

Această relație de echivalență este dreapta-invariantă dacă:

{\hat {\delta }}\left(q_{0},xz\right)={\hat {\delta }}\left({\hat {\delta }}\left(q_{0},x\right),z\right)={\hat {\delta }}\left({\hat {\delta }}\left(q_{0},y\right),z\right)={\hat {\delta }}\left(q_{0},yz\right)

{\ displaystyle {\ hat {\ delta}} \ left (q_ {0}, xz \ right) = {\ hat {\ delta}} \ left ({\ hat {\ delta}} \ left (q_ {0} , x \ right), z \ right) = {\ hat {\ delta}} \ left ({\ hat {\ delta}} \ left (q_ {0}, y \ right), z \ right) = {\ pălărie {\ delta}} \ left (q_ {0}, yz \ right)}

{\ displaystyle {\ hat {\ delta}} \ left (q_ {0}, xz \ right) = {\ hat {\ delta}} \ left ({\ hat {\ delta}} \ left (q_ {0} , x \ right), z \ right) = {\ hat {\ delta}} \ left ({\ hat {\ delta}} \ left (q_ {0}, y \ right), z \ right) = {\ pălărie {\ delta}} \ left (q_ {0}, yz \ right)}

presupunând

xR_{M}y

{\ displaystyle xR_ {M} y}

{\ displaystyle xR_ {M} y}

.

Enunțarea teoremei

Teorema Myhill-Nerode afirmă că afirmațiile sunt echivalente:

$L\subseteq \Sigma ^{*}$ ${\ displaystyle L \ subseteq \ Sigma ^ {*}}$ ${\ displaystyle L \ subseteq \ Sigma ^ {*}}$ este regulat
$L$ ${\ displaystyle L}$ $L$ este uniunea unor clase de echivalență ale unei relații de echivalență a indexului finit (adică care identifică un număr finit de clase de echivalență ) invariante la dreapta
relația de echivalență: $\forall x,y\in \Sigma ^{*},xR_{L}y\Longleftrightarrow \forall z\in \Sigma ^{*},xz\in L\Longleftrightarrow yz\in L$ ${\ displaystyle \ forall x, y \ in \ Sigma ^ {*}, xR_ {L} y \ Longleftrightarrow \ forall z \ in \ Sigma ^ {*}, xz \ in L \ Longleftrightarrow yz \ in L}$ ${\ displaystyle \ forall x, y \ in \ Sigma ^ {*}, xR_ {L} y \ Longleftrightarrow \ forall z \ in \ Sigma ^ {*}, xz \ in L \ Longleftrightarrow yz \ in L}$ este de indice finit.

Utilizări și consecințe

Consecința directă a teoremei Myhill-Nerode este că un limbaj $L$ ${\ displaystyle L}$ $L$ este regulat dacă și numai dacă numărul claselor de echivalență ale relației $R_{L}$ ${\ displaystyle R_ {L}}$ ${\ displaystyle R_ {L}}$ s-a terminat. Ca corolar, un limbaj care definește un set infinit de clase de echivalență nu este regulat. Acest corolar poate fi folosit pentru a demonstra neregularitatea unei limbi.

Bibliografie

( EN ) Anil Nerode, Linear Automaton Transformations ( PDF ), în Proceedings of the American Mathematical Society , vol. 9, nr. 4, august 1958, pp. 541-544. Adus la 11 iunie 2011 .
( EN ) Jan van Leeuwen, Limite inferioare: teoria limbajului formal , în Handbook of Theoretical Computer Science, Vol. A: Algorithms and Complexity , The MIT Press, 4 ianuarie 1994, ISBN 978-0-262-72014-4 .
(EN) Martin Davis , Ron Sigal; Elaine J. Weyuker, The Myhill-Nerode Theorem , in Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science , Morgan Kaufmann, 17 februarie 1994, ISBN 978-0-12-206382-4 .

Elemente conexe

Lemă de pompare pentru limbi obișnuite

Portal IT : accesați intrările Wikipedia care se ocupă cu IT