Come a dimostrare che una lingua non è regolare?

https://cs.stackexchange.com/questions/1031

16-10-2019
|

Domanda

Abbiamo imparato a conoscere la classe dei linguaggi regolari $ \ mathrm {} REG $. E 'caratterizzata da una qualsiasi concezione tra le espressioni regolari, automi a stati finiti e grammatiche sinistra lineari, quindi è facile dimostrare che un determinato linguaggio è regolare.

Come posso mostrare il contrario, però? La mia TA è stato fermamente convinto che, al fine di farlo, dovremmo spettacolo per tutte le espressioni regolari (o per tutti automi a stati finiti, o per tutte le grammatiche sinistra-lineari) che non possono descrivere la lingua a portata di mano. Questo mi sembra un grande compito!

Ho letto su alcuni di pompaggio lemma ma sembra davvero complicato.

^{Questo è destinato ad essere una questione di riferimento raccolta usuali metodi di prova ed esempi di applicazione. Vedere qui per la stessa domanda sui linguaggi liberi dal contesto.}

Soluzione

La prova per assurdo è spesso usato per mostrare che una lingua non è regolare: sia $ P $ un immobile vale per tutti i linguaggi regolari, se il linguaggio specifico non verifica $ P $, allora non è regolare. Le seguenti proprietà possono essere utilizzati:

Il lemma di pompaggio, come esemplificato in di Dave risposta ;
proprietà di chiusura dei linguaggi regolari (operazioni di set, concatenazione, Kleene stella, specchio, homomorphisms);
Un linguaggio regolare ha un numero finito di prefisso di classe di equivalenza, Myhill-Nerode teorema .

Per dimostrare che una lingua $ L $ non è regolare utilizzando le proprietà di chiusura, la tecnica è quella di combinare $ L $ con i linguaggi regolari operazioni che preservano la regolarità al fine di ottenere una lingua conosciuta per essere non regolare, ad esempio, l'archetipo lingua $ I = \ {a ^ nb ^ n | n \ in \ mathbb {N} \} $. Per esempio, diciamo $ L = \ {a ^ p b ^ q | p \ neq q \} $. Si supponga $ L $ è regolare, come linguaggi regolari sono chiusi sotto complementazione modo è $ L $ 's complemento $ L ^ c $. Ora prendete l'intersezione di $ L ^ c $ e $ a ^ \ stella b ^ \ stella $ che è regolare, si ottiene $ I $, che non è regolare.

Il Myhill-Nerode teorema può essere utilizzata per dimostrare che $ I $ non è regolare. Per $ p \ geq 0 $, $ I / a ^ p = \ {a ^ {r} b ^ rb ^ p | r \ in \ mathbb {N} \} = I. \ {b ^ p \} $. Tutte le classi sono diverse e c'è un'infinità numerabile di tali classi. Come un linguaggio regolare deve avere un numero finito di classi $ I $ non è regolare.

Altri suggerimenti

In base alla risposta di Dave, ecco un passo passo "manuale" per l'uso del lemma di pompaggio.

Recall il lemma di pompaggio (preso dalla risposta di Dave, preso forma Wikipedia):

Sia $ L $ essere un linguaggio regolare. Allora esiste un intero $ n \ ge 1 $ (che dipende solo da $ L $ ) in modo tale che ogni stringa di $ w $ in $ L $ di lunghezza almeno $ n $ ( $ n $ è chiamata la "lunghezza di pompaggio") può essere scritto come $ w = xyz $ (vale a dire, $ w $ può essere diviso in tre sottostringhe), che soddisfa le seguenti condizioni:

$ | y | \ Ge 1 $

$ | xy | \ Le n $ e

un "pompato" $ w $ è ancora in $ L $ : per tutti $ i \ ge 0 $ , $ xy ^ iz \ in L $ .

Si supponga che si è data una certa lingua $ L $ e si vuole dimostrare che non è regolare tramite il lemma di pompaggio. Gli sguardi a prova di come questo:

Si supponga che $ L $ regolare.
Se è regolare, allora il lemma di pompaggio dice che esiste un certo numero di $ n $ che è la lunghezza di pompaggio.
Scegli un specifica parola $ w \ in L $ di lunghezza maggiore di $ n $ . La parte difficile è sapere quale parola da prendere.
Si consideri tutti i modi di partizione $ w $ in 3 parti, $ w = xyz $ , con $ | xy | \ le n $ e $ y $ non vuoto . Per ogni di questi modi, spettacolo che non può essere pompato: esiste sempre un po 'di $ i \ ge 0 $ in modo tale che $ xy ^ iz \ notin L $ .
Concludere: la parola $ w $ non può essere "pompato" (non importa come abbiamo diviso per $ xyz $ ) in contraddizione con il lemma di pompaggio, vale a dire, la nostra ipotesi (fase 1) è sbagliato: $ L $ non è regolare

Prima di andare ad un esempio, mi permetta di ribadire Step 3 e Step 4 (questo è dove la maggior parte delle persone andare male). Nel passaggio 3 è necessario scegliere una parola specifica in $ L $ . scriverlo esplicitamente, come "00001111" o " $ a ^ nb ^ n $ ". Esempi di cose che sono non una parola specifica:. " $ w $ " o "una parola che ha 000 come prefisso"

D'altra parte, al punto 4 è necessario considerare più di un caso. Per esempio, se $ w = 000.111 $ non è sufficiente dire $ x = 00, y = 01, z = 00 $ , e poi raggiungere una contraddizione. È inoltre necessario verificare $ x = 0, y = 0, z = 0111 $ , e $ x = \ epsilon, y = 000, z = 111 $ , e tutte le altre opzioni possibili.

Ora diamo seguire i passi e dimostrano che $ L = \ {0 ^ k1 ^ {2k} \ metà k> 0 \} $ non è regolare.

Si supponga $ L $ è regolare.
Let $ n $ la lunghezza di pompaggio proposta dal lemma di pompaggio.
Let $ w = 0 ^ n 1 ^ {2n} $ .
(Controllo di integrità: $ | w | \ n gt $ se necessario. Perché questa parola? altre parole possono funzionare come bene .. ci vuole una certa esperienza a venire con il diritto $ w $ ). Anche in questo caso, si noti che $ w $ è una parola specifica: $ \ underbrace {000 \ ldots0} _ {n \ text { volte}} \ {underbrace 111 \ ldots1} _ {2n \ text {volte}} $ .
Ora lascia iniziare prendere in considerazione i vari casi di scissione $ w $ in $ xyz $ con $ | xy | \ le n $ e $ | y |> 0 $ . Dal momento che $ | xy | non importa quanto abbiamo diviso $ w $ , $ x $ sarà composto di soli 0 e così sarà $ y $ . Consente di assumere $ | x | = s $ e $ | y | = k $ . Dobbiamo considerare tutte le opzioni, che è tutto il possibile $ s, k $ in modo tale che $ s \ ge 0, k \ ge 1 $ e $ s + k \ le n $ . PER QUESTO $ L $ la prova per tutti questi casi è lo stesso, ma in generale potrebbe essere diverso.
prendere $ i = 0 $ e considerare $ xy ^ iz = XZ $ . Questa parola non è in $ L $ dal momento che è di forma $ 0 ^ {nk} 1 ^ {2n} $ (non importa quale $ s $ e $ k $ erano), e dal momento che $ k \ ge 1 $ , questa parola non è in $ L $ e raggiungiamo una contraddizione.
Quindi, la nostra ipotesi è corretta, e $ L $ non è regolare.

Un youtube clip che si spiega come utilizzare il lemma di pompaggio lungo le stesse linee si possono trovare qui

Da Wikipedia, la lingua di pompaggio per linguaggi regolari è la seguente:

Sia $ L $ un linguaggio regolare. Quindi esiste un intero $ p \ ge 1 $ (dipendente solo $ L $) in modo tale che ogni stringa $ w $ in $ L $ di lunghezza almeno $ p $ ($ p $ è chiamata la "lunghezza di pompaggio") can essere scritta da $ w = xyz $ (cioè, $ w $ può essere diviso in tre sottostringhe), che soddisfa le seguenti condizioni:

$ | y | \ Ge 1 $

$ | xy | \ Le p $ e

per tutti i $ \ ge 0 $, $ xy ^ iz \ in L $.
$ Y $ è la stringa secondaria che può essere pompato (rimosso o ripetuto quante volte, e la stringa risultante è sempre in $ L $).

(1) indica il ciclo y essere pompata deve essere di lunghezza almeno uno; (2) significa il ciclo deve avvenire entro i primi caratteri p. Non ci sono restrizioni su xe z.

In parole semplici, per ogni linguaggio regolare L, qualsiasi sufficientemente lungo termine $ w \ in L $ può essere suddiviso in 3 parti. cioè $ w = xyz $, in modo tale che tutte le stringhe $ xy ^ KZ $ a $ k \ ge 0 $ sono anche in $ L $.

Consideriamo ora un esempio . Sia $ L = \ {(01) ^ n2 ^ n \ mid n \ GE0 \} $.

Per mostrare che questo non è regolare, è necessario considerare quello che tutte le decomposizioni $ w = xyz $ assomigliare, così che cosa sono tutte le cose possibili X, Y e Z può essere dato che $ xyz = (01) ^ p2 ^ p $ (abbiamo scelto di guardare a questo particolare parola, di lunghezza $ 3p $, dove $ p $ è la lunghezza di pompaggio). Dobbiamo considerare in cui si verifica il $ y $ parte della stringa. Potrebbe sovrapporsi alla prima parte, e sarà quindi uguale o $ (01) ^ {k + 1} $, $ (10) ^ {k + 1} $, $ 1 (01) ^ k $ o $ 0 (10) ^ k $, per un po '$ k \ ge 0 $ (non dimenticate che $ | y | \ ge 1 $). Potrebbe sovrapporsi con la seconda parte, il che significa che $ y = 2 ^ k $, per qualche $ k> 0 $. Oppure potrebbe sovrapporsi tra le due parti della parola, ed avrà la forma $ (01) ^ {k + 1} 2 ^ l $, $ (10) ^ {k + 1} 2 ^ l $, $ 1 (01 ) ^ k 2 ^ l $ o $ 0 (10) ^ k 2 ^ l $, per $ k \ GE0 $ e $ l \ GE1 $.

Ora pompa ciascuno per ottenere una contraddizione, che sarà un non parole nella tua lingua. Ad esempio, se prendiamo $ y = 0 (10) ^ k2 ^ l $, il lemma di pompaggio dice, per esempio, che $ xy ^ 2z = x0 (10) ^ k2 ^ l0 (10) ^ k2 ^ lz $ must nella lingua, per una scelta appropriata di $ x $ e $ Z $. Ma questa parola non può essere nella lingua come $ 2 $ appare prima di un $ 1 $.

Altri casi comporterà il numero di $ 'S è superiore al numero di $ 2 $' (01) $ s o viceversa, o si tradurrà in parole che non avranno la struttura $ (01) ^ n2 ^ n $ da, per esempio, avente due $ 0 $ 's in una riga.

Non dimenticare che $ | xy | \ Le p $. Qui, è utile per accorciare la prova:. Molte delle scomposizioni di cui sopra sono impossibili, perché renderebbe il $ parte $ z troppo tempo

Ciascuno dei casi sopra necessità di condurre ad una tale contraddizione, che sarebbe allora una contraddizione del lemma di pompaggio. Ecco! La lingua non sarebbe regolare.

Per una data lingua $ L \ subseteq \ Sigma ^ * $, lasciare

$ \ qquad \ displaystyle s_l (z) = \ sum \ limits_ {n \ geq 0} | L \ cappello \ Sigma ^ n | \ cdot z ^ n $

la (ordinario) funzione generatrice di $ L $, vale a dire la sua sequenza di conteggio delle parole per lunghezza.

La seguente dichiarazione detiene [ FlSe09 , p52]:

$ \ qquad \ displaystyle L \ in \ mathrm {REG} \ quad \ Longrightarrow \ quad s_l \ text {} razionale $

Cioè, $ s_l (z) = \ frac {P (z)} {Q (z)} $ con $ P, Q $ polinomi.

Quindi, qualsiasi lingua la cui funzione generatrice è non razionale non è regolare. Purtroppo, tutte le lingue href="https://en.wikipedia.org/wiki/Linear_language"> hanno anche functions¹ generazione razionale quindi questo metodo non funziona per i più semplici lingue non regolari. Un altro svantaggio è che l'ottenimento di $ s_l $ (e mostrando che non è razionale) può essere difficile.

Esempio: Si consideri il linguaggio delle parentesi correttamente annidati parole, vale a dire la Dyck lingua . Si è generato dal inequivocabile grammatica

$ \ qquad \ displaystyle S \ a [S] S \ mid \ varepsilon $

che può essere tradotto nell'equazione

$ \ qquad \ displaystyle S (z) = z ^ 2S ^ 2 (z) + 1 $

una soluzione (quello con tutti i coefficienti positivi) di cui è

$ \ qquad \ displaystyle \ mathcal {S} (z) = \ frac {1 - \ sqrt {1 - 4z ^ 2}} {2z ^ 2} $.

$ s_l = \ mathcal {S} $ [ Kuic70 ] e $ \ mathcal {S } $ non è razionale, la lingua Dyck non è regolare.

La prova per la dichiarazione per linguaggi regolari funziona tramite grammatiche e trasferimenti da grammatiche lineari immediatamente (proprietà commutativa della moltiplicazione).

$ \ \ $ [FlSe09] Analytic Combinatorics by P. Flajolet e R. Sedgewick (2009)
$ \ \ $ [Kuic70] Al Entropy di Context-free Languages ?? da W. Kuich (1970)

Questa è una versione ampliata della mia risposta da qui Utilizzo di pompaggio Lemma per provare lingua $ L = \ {(01) ^ m 2 ^ m \ m metà \ GE0 \} $ non è regolare in quanto questo dovrebbe essere una questione di riferimento.

Quindi, pensi che gli sguardi di pompaggio lemma complicato? Non si preoccupi. Ecco un po 'diverso approccio ripresa, che è nascosto nel @ risposta di Romuald pure. (Quiz: dove)

La partenza di Let ricordando che ogni linguaggio regolare è accettato da un automa a stati finiti deterministico (DFA). Un DFA è un grafo finito diretto dove ogni vertice ha una e una sola punta per ogni lettera dell'alfabeto. Strings ti danno una passeggiata nel grafico in base ad un vertice con l'etichetta "start", e il DFAE accetta se questa passeggiata termina in un vertice etichettati "accetta". (I vertici sono chiamati "stati", perché diverse aree della matematica, come per compensare la propria terminologia per la stessa cosa).

Con questo modo di pensare è facile vedere che: Se le stringhe $ a $ e $ B $ guidare il DFA allo stesso stato, quindi per qualsiasi altra stringa $ c $, $ AC $ e $ bc $ guidare il DFA nello stesso stato. Perché? Perché il punto affermando di una passeggiata e la stringa definendolo determinare completamente alla fine.

Put in modo leggermente diverso: Se $ L $ è regolare e le stringhe $ a $ e $ b $ guidare un automa che riconosce allo stesso stato, poi per tutte le stringhe $ C $, o $ AC $ e $ bc $ sono entrambi in $ L $ o nessuno dei due è.

Si può usare questo per mostrare le lingue non sono regolari immaginando che è e poi venire con $ a $ e $ b $ alla guida di una DFA allo stesso stato, e $ c $ in modo che $ AC $ è nella lingua e $ bc $ non lo è. Prendete il linguaggio esempio da @ risposta di Dave. Immaginate è regolare, quindi ha un po 'di riconoscere DFA con $ M $ Stati. Il principio dei cassetti dice che almeno due dei $ \ {(01) ^ i: 0 \ le i \ le m + 1 \} $ inviare il DFA allo stesso stato, ad esempio $ a = (01) ^ p $ e $ b = (01) ^ q $. Dal momento che $ p \ neq q $, vediamo che $ a2 ^ p $ è nella lingua e $ b2 ^ p $ non è, quindi questo linguaggio non può essere regolare.

La cosa bella è che l'esempio è davvero un modello per dimostrare che le lingue non sono regolari:

Trova una famiglia di stringhe $ \ {A_i: i \ in \ mathbb {N} \} $ con la proprietà che ciascuno di loro ha una "coda" $ t_i $ in modo che $ a_it_i $ è nella lingua e $ a_it_j $, per $ i \ neq j $ non è.
Applicare l'argomento sopra parola per parola. (Ciò è consentito, dato che ci sono sempre abbastanza $ A_i $ per farvi invocare il principio Pigeon Hole.)

Ci sono altri trucchi, ma questo funzionerà facilmente sulla maggior parte dei vostri problemi a casa.

Modifica:. Una versione precedente ha avuto qualche discussione su come questa idea si riferisce al Pumping Lemma

A seguito della risposta qui , mi limiterò a descrivere un metodo di prova non regolarità sulla base di Kolmogorv complessità.

Questo approccio è discusso in "Un nuovo approccio alla teoria dei linguaggi formali per Kolmogorov Complessità ", da Ming Li e Paul M.B. Vitanyi (vedere paragrafo 3.1).

Sia $ K (x) $ denotano la complessità Kolmogorov di una stringa $ x $, cioè la lunghezza del minimo codifica di una macchina di Turing $ M $, tali che $ M (\ epsilon) = x $ (qualsiasi le definizioni usuali farà). Si può quindi utilizzare il seguente lemma di dimostrare non regolarità:

KC-Regolarità : Sia $ L \ subseteq \ Sigma ^ * $ un linguaggio regolare, allora esiste una costante $ C $ che dipende solo $ L $, tale che per ogni $ x \ in \ Sigma ^ * $, se $ y $ è il $ n'th $ string (rispetto al ordinamento lessicografico) a $ L_x = \ left \ {y \ in \ Sigma ^ * | xy \ a L \ right \} $, allora $ K (y) \ le O (\ log n) + c $.

Si può capire (e dimostrare) il lemma di cui sopra come segue, per ogni $ x \ in \ Sigma ^ * $, per descrivere il $ stringa $ n'th a $ L_x $ si ha la necessità di specificare:

L'automa che accetta $ L $
Lo stato in l'automa dopo l'elaborazione del prefisso $ x $
L'indice $ n $

Dato che abbiamo solo bisogno di ricordare lo stato dopo l'elaborazione $ x $, e non $ x $ in sé, possiamo nascondere questo fattore nella costante a seconda $ L $. L'indice di $ n $ richiede $ \ log n $ bit per descrivere, e si ottiene il risultato di cui sopra (per completezza, bisogna aggiungere le istruzioni specifiche richieste per generare $ y $, ma questo aggiunge solo un fattore costante alla descrizione finale ).

Questa lemma mostra come vincolata la complessità di Kolmogorov di tutte le stringhe che sono membri di $ L_x $ per un certo linguaggio regolare $ L $ e $ x \ in \ Sigma ^ * $. Al fine di mostrare non regolarità, si può assumere $ L $ è regolare, e dimostrano che i limiti sono troppo restrittivi (complessità Kolmogrov esempio delimitata per un insieme infinito di stringhe).

La risposta linkato sopra contiene un esempio di come usare questo lemma per mostrare $ L = \ left \ {1 ^ p | \ Text {p è primo} \ right \} $ non è regolare, molti altri esempi sono riportati nella carta. Per completezza, mostriamo qui come dimostrare $ L = \ left \ {0 ^ n1 ^ n | n \ ge 0 \ right \} $ non è regolare.

Dato un $ x \ in \ left \ {0,1 \ right \} ^ * $, indichiamo con $ y_i ^ x $ i $-esimo $ parola in $ L_x $. Si noti che $ y_1 ^ {0 ^ i} = 1 ^ i $. Utilizzando quanto sopra lemma, concentrandosi su prefissi $ x $ di forma $ x = 0 ^ i $ e fissaggio $ n = 1 $, si ottiene $ \ forall i \ ge 0: K (y_1 ^ {0 ^ i}) \ Le c $. Poiché $ y_1 ^ {0 ^ i} = 1 ^ i $, ciò significa che possiamo legati alla complessità di Kolmogorov di tutte le stringhe della forma $ 1 ^ i $ per una costante, che è ovviamente falso. Vale la pena ricordare che potremmo esaminato un singolo $ x $, ad esempio $ X = 0 ^ n $ per grandi $ abbastanza n $ che soddisfa $ K (0 ^ n) \ ge \ log n $ (si parte con un prefisso ad alta complessità). Dal momento che $ y_1 ^ x = 1 ^ n $, otteniamo $ K (1 ^ n) 2 ^ c $).

Nel caso di lingue unari (lingue oltre un alfabeto di misura 1), v'è un criterio semplice. Fissiamo un alfabeto $ \ {\ sigma \} $, e per $ A \ subseteq \ mathbb {N} $, definire $$ L (A) = \ {\ sigma ^ n: n \ in A \}. $$

Teorema. Sia $ A \ subseteq \ mathbb {N} $. Di seguito sono equivalenti:

L $ (A) $ è regolare.

L $ (A) $ è context-free.

Non esiste $ n_0, m \ geq 1 $ tale che per ogni $ n \ geq n_0 $, si sostiene che $ n \ in A $ se e solo se $ n + m \ in A $. (Diciamo che $ A $ è alla fine periodico ).

Sia $ A_i = 1_ {i \ in A} $. Poi $ 0.a_0a_1a_2 \ ldots $ è razionale.

La funzione generatrice $ \ sum_ {i \ in A} x ^ $ i è una funzione razionale.

Il teorema può essere provato in molti modi, ad esempio utilizzando il lemma di pompaggio, la teoria Myhill-Nerode, il teorema di Parikh, la struttura dei DFA su linguaggi unari (appaiono come un "$ \ rho $", come in $ di Pollard \ rho $ algoritmo), e così via. Qui è un corollario utile.

Corollario. Sia $ A \ subseteq \ mathbb {N} $, e supponiamo che $ L (A) $ è regolare.

Il limite $ \ rho = \ lim_ {n \ to \ infty} \ frac {| A \ cap \ {1, \ ldots, n \} |} {n} $ esiste. (Questo è il densità asintotica di $ A $.)

Se $ \ rho = 0 $ allora $ A $ è finito.

Se $ \ rho = 1 $ quindi $ A $ è cofinite (cioè, $ \ overline {A} $ è finito).

A titolo di esempio, la lingua $ L (\ {2 ^ n: n \ geq 0 \}). $ Non è regolare, dal momento che l'insieme ha fuga densità asintotica, eppure è infinita

La classe dei linguaggi regolari è closured sotto varie operazioni di chiusura, come unione, intersezione, complemento, homomorphism, la sostituzione regolare, inversa omomorfismo, e altro ancora. Questo può essere usato per dimostrare che una determinata lingua non è regolare con la riduzione ad un linguaggio che è già noto per essere non regolare.

Come un semplice esempio, si supponga che sappiamo che il linguaggio $ \ {a ^ nb ^ n: n \ geq 0 \} $ non è regolare. Poi possiamo dimostrare che la lingua $ \ {w \ in \ {a, b \} ^ *: \ #_ un (w) = \ #_ b (w) \} $ (il linguaggio di tutte le parole con altrettanto molti $ a $ s e $ b $ s) non è regolare come segue:

Si supponga che $ L = \ {w \ in \ {a, b \} ^ *: \ #_ un (w) = \ #_ b (w) \} $ erano regolari. Poi $ L \ tappo a ^ * b ^ * $ sarebbe anche normale. Ma $ L \ tappo a ^ * b ^ * = \ {a ^ nb ^ n: n \ geq 0 \} $ , che è noto per non essere regolare.

Ecco un esempio più complicato. Mostriamo che il linguaggio $ L'= \ {(0 + 1) ^ n2 (0 + 1) ^ n: n \ geq 0 \} $ non è regolare.

Sia $ h $ essere la mappatura omomorfismo dato da $ h (0) = 0 $ , $ h (1) = 1 $ , $ h (2) = \ epsilon $ . Se $ L '$ erano regolari allora così sarebbe il seguente linguaggio sia: $ h (L' \ cap 0 ^ * 21 ^ *) = \ {0 ^ n 1 ^ n: n \ geq 0 \} $ . Tuttavia, sappiamo che quest'ultimo non è regolare.

Infine, ecco un esempio utilizzando omomorfismo inversa. Mostriamo che il linguaggio $ L '' = \ {0 ^ n10 ^ n: n \ geq 0 \}. $ non è regolare

Let $ k $ essere l'omomorfismo dato da $ k (0) = 0 $ , < span class = "math-contenitore"> $ k (1) = 0 $ , $ k (2) = 1 $ . Se $ L '' $ erano regolari allora così sarebbe $ k ^ {- 1} (L '') $ essere, ma che è solo la lingua $ L '$ dall'esempio precedente.

teoria Usa Myhill-Nerode.

Sia $ L $ essere una lingua. Diciamo che due parole $ x, y $ inequivalenti modulo $ L $ (o: rispetto a $ L $ ) se esiste una parola $ Z $ tale che esattamente uno dei $ XZ, YZ $ è in $ L $ . In ogni DFA per $ L $ , $ \ delta (Q_0, x) \ neq \ delta (Q_0, y) $ (esercizio). Ciò implica il seguente criterio:

Sia $ L $ essere una lingua. Supponiamo che esista un insieme infinito di parole a coppie non equivalenti (cioè, un insieme infinito $ S $ in modo tale che ogni due non-uguale $ x, y \ in S $ sono modulo inequivalenti $ L $ ). Poi $ L $ non è regolare.

Ecco un semplice esempio di applicazione di tale criterio:

Il lingua $ L = \ {a ^ nb ^ n: n \ geq 0 \}. $ non è regolare

Prova Let $ S = \ {a ^ n: n \ geq 0 \}. $ . Noi affermiamo che ogni due parole diverse in $ S $ sono modulo inequivalenti $ L $ . Infatti, lasciare $ a ^ i, a ^ j \ in S $ , dove $ i \ ne j $ . Poi $ a ^ ib ^ i \ in L $ ma $ a ^ ib ^ j \ notin L $ .

Una caratteristica importante di questo metodo è che è garantito per avere successo: se $ L $ non è regolare, allora esiste un insieme infinito di parole a coppie non equivalenti. Questa è una conseguenza della Myhill-Nerode teorema . Brevemente, l'equivalenza modulo $ L $ (la negazione di inequivalenza modulo $ L $ definito sopra) è un'equivalenza relazione, e un linguaggio $ L $ è regolare se e solo se il numero di classe di equivalenza di equivalenza modulo $ L $ è finito. Se $ L $ non è regolare, prendendo una parola di ogni classi di equivalenza costituirebbero un insieme infinito di parole non equivalenti.

Dato un linguaggio $ L $ , per ogni stringa di $ x $ v'è un insieme di stringhe $ y $ in modo tale che $ xy \ in L $ . Una simile serie potrebbe essere usato come uno stato in una macchina a stati.

Tutto quello che devi fare è quello di mostrare che il numero di tali insiemi non è finita.

Per fare un esempio, lasciare $ L = {a ^ nb ^ n: n = 0} $ . Dato $ x = a ^ nb $ per un po ' $ n = 1 $ , l'unica stringa di $ y $ in modo tale che $ xy \ in L $ $ y = b ^ {n-1} $ . Quindi per ogni $ n $ abbiamo un diverso insieme, il che significa $ L $ non è regolare.

Quindi, in generale, se si trova un insieme infinito di stringhe $ x $ in modo tale che ogni $ x $ dà un diverso insieme $ \ {y: xy \ a L \} $ quindi la lingua non può essere riconosciuto da una macchina a stati finiti, e quindi non è regolare.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a cs.stackexchange