Come si può dimostrare che una lingua è regolare?

Esistono diversi modi per dimostrare che una lingua è regolare. Ecco una rottura dei metodi comuni, insieme a spiegazioni ed esempi:

1. Costruire un automatico finito (FA) o deterministico Automate finito (DFA)

* Spiegazione: Se puoi costruire un DFA o NFA (automobile finito non deterministico) che accetta * tutto * e * solo * le stringhe nella lingua, allora la lingua è regolare.

* Come farlo:

* Definisci gli stati: Gli stati della tua FA rappresentano la "memoria" di ciò che è stato visto finora nella stringa di input. Pensa a quali informazioni sono essenziali per ricordare di determinare se la stringa è nella lingua.

* Definisci le transizioni: Le transizioni determinano il modo in cui la FA si sposta da stato a stato in base ai simboli di input. Assicurati che le tue transizioni riflettano correttamente le regole della lingua.

* Definisci lo stato di partenza: Dove l'automa inizia l'elaborazione.

* Definisci gli stati accettanti: Gli stati che indicano la stringa sono nella lingua.

* Esempio: Considera la lingua l ={stringhe su {a, b} che contengono "ab" come sottostringa}.

`` `

Stati:Q0 (Start), Q1, Q2 (accettazione)

Transizioni:

- Q0, A -> Q1 (visto un 'A' finora, potenzialmente porta a "AB")

- Q0, B -> Q0 (visto a 'B', reset)

- Q1, A -> Q1 (visto 'AA' finora, ancora alla ricerca di "AB")

- Q1, B -> Q2 (visto 'AB'!)

- Q2, A -> Q2 (già visto 'AB', quindi ogni ulteriore input ci fa accettare)

- Q2, B -> Q2 (già visto 'AB', quindi ogni ulteriore input ci fa accettare)

State State:Q0

Accettazione dello stato:Q2

`` `

Puoi disegnare un diagramma di stato per visualizzare questa FA.

2. Costruire un'espressione regolare

* Spiegazione: Se riesci a scrivere un'espressione regolare che descrive * tutte * e * solo * le stringhe nella lingua, allora la lingua è regolare.

* Come farlo:

* Comprendi gli operatori di espressione regolare di base:

* Concatenation:`AB` (abbina la stringa" AB ")

* Unione (o):`a | b` (corrispondenze" a "o" b ")

* Kleene Star (zero o più ripetizioni):`a*` (abbina "", "a", "aa", "aaa", ...)

* Kleene Plus (una o più ripetizioni):`a+` (corrisponde "a", "aa", "aaa", ...)

* Parentesi per il raggruppamento:`(a | b) c` (corrisponde a" ac "o" bc ")

* Classi di personaggi:`[ABC]` (abbina 'a', 'b' o 'c')

* Gamme:`[a-z]` (abbina qualsiasi lettera minuscola)

* Abbattere il linguaggio in parti più piccole e combinarle usando gli operatori.

* Esempio: Usando la stessa lingua l ={stringhe su {a, b} che contengono "ab" come sottostringa}.

L'espressione regolare è:`(a | b)*ab (a | b)*`

* `(A | B)*` significa zero o più occorrenze di 'A' o 'B' (qualsiasi stringa di 'A e' B).

* `AB` è la sottostringa richiesta.

* `(A | B)*` consente di nuovo qualsiasi stringa di 'A e' B's* dopo* "AB".

3. Utilizzo delle proprietà di chiusura delle lingue regolari

* Spiegazione: Le lingue regolari sono chiuse sotto determinate operazioni. Ciò significa che se si applica queste operazioni a lingue regolari, il risultato è anche una lingua normale. Le proprietà di chiusura comuni includono:

* Unione

* Concatenazione

* Kleene Star

* Intersezione

* Complementazione

* Differenza

* Inversione

* Omomorfismo (sostituzione)

* Come farlo:

1. Mostra che la lingua può essere costruita da linguaggi regolari più semplici e noti utilizzando le operazioni di chiusura.

2. Ad esempio, se puoi dimostrare che la tua lingua è l'unione di due lingue regolari, hai dimostrato che è regolare.

* Esempio: Sia l1 ={stringhe su {a, b} a partire da 'a'} e l2 ={stringhe su {a, b} che terminano con 'b'}. Sia L1 che L2 sono regolari (puoi facilmente scrivere espressioni regolari per loro:`a (a | b)*` e `(a | b)*b`).

Ora, considera la lingua l =l1 ∩ l2 ={stringhe su {a, b} a partire da 'a' * e * terminando con 'b'}.

Poiché le lingue regolari sono chiuse sotto l'intersezione, L è anche regolare. La sua espressione regolare è `a (a | b)*b`.

4. Teorema myhill-nnerode

* Spiegazione: Il teorema di Myhill-nnerode fornisce una condizione necessaria e sufficiente affinché una lingua sia regolare. Dichiara che una lingua L è regolare se e solo se ha un numero finito di *suffissi distinguibili *. Due suffissi *x *e *y *sono distinguibili rispetto a *l *se esiste una stringa *z *tale che esattamente una di *xz *o *yz *è in *l *. In termini più semplici:una lingua L è regolare se puoi dividere tutti i possibili prefissi in un numero finito di classi di equivalenza.

* Come farlo (più avanzato):

1. Definire una relazione di equivalenza basata su suffissi distinguibili:`x ≡ y` se e solo se per tutte le stringhe` z`, `xz ∈ L` se e solo se` yz ∈ L`.

2. Mostra che il numero di classi di equivalenza in questa relazione è finito. Se lo è, allora la lingua è regolare. Il numero di classi di equivalenza è uguale al numero di stati nel DFA minimo per la lingua.

* Esempio: Let l ={0 n 1 n | n ≥ 0}. Questo è un linguaggio * non regolare * (usato per dimostrare il lemma di pompaggio). Per comprendere intuitivamente l'applicazione Myhill-nnerode:

Considera i prefissi 0, 00, 000, .... Se L era regolare, quindi alla fine due prefissi, diciamo 0 i e 0 J (dove io i a 0 i , ottieni 0 i 1 i , che * è * in L. Tuttavia, se aggiungi 1 i a 0 j , ottieni 0 j 1 i , che * non * in l (perché j> i). Quindi, 0 i e 0 J sono distinguibili. Poiché puoi creare un numero infinito di prefissi distinguibili, la lingua non è regolare. Il teorema di Myhill-nerode è spesso usato per dimostrare che una lingua * non * regolare.

5. Il lemma di pompaggio per le lingue regolari (per dimostrare che una lingua non è * normale)

* Spiegazione: Il lemma di pompaggio è uno strumento per dimostrare che una lingua non è * regolare. Afferma che se una lingua l è regolare, esiste una lunghezza di pompaggio *P *(un numero intero), tale che qualsiasi stringa *s *in l con lunghezza maggiore o uguale a *p *può essere divisa in tre substrazioni, *x *, *y *e *z *, dove *s *=*xyz *, e le seguenti condizioni detengono:

1. Per ogni i> =0, xy i Z è in L. (è possibile "pompare" la parte y in ogni numero di volte e il risultato è ancora nella lingua).

2. | Y |> 0. (La parte Y "pompata" deve avere una lunghezza almeno 1).

3. | xy | <=p. (La parte "pompata" deve verificarsi all'interno dei primi caratteri P).

* Come usarlo per dimostrare la non regolare:

1. Supponiamo che l sia regolare.

2. Supponiamo che la lunghezza di pompaggio sia *P *. (Non sai cosa sia * p *, ma presumi che esista).

3. Scegli una stringa * s * in l tale che | s |> =*p *. La chiave qui è scegliere una stringa * s * che porterà a una contraddizione in seguito. Questa è spesso la parte più difficile.

4. Considera tutti i modi possibili per dividere * s * in * xyz * tale che | y |> 0 e | xy | <=*p *.

5. Per *ciascuno *Possibile divisione, trova un valore di *i *tale che *xy i z* non* non* in l. Questo contraddice il lemma di pompaggio, che dice che * per tutti * i, xy i Z deve essere in L.

6. Da quando hai trovato una contraddizione, la tua ipotesi iniziale che L sia regolare deve essere falsa. Pertanto, L non è regolare.

* Esempio: Let l ={a n B n | n> =0}. Dimostra che L non è regolare.

1. Supponiamo che l sia regolare.

2. Let * p * sia la lunghezza di pompaggio.

3. Scegli * s * =a p B p . Si noti che | s | =2p> =p.

4. Considera le possibili divisioni di * s * in * xyz * con | y |> 0 e | xy | <=*p *. Dal momento che | xy | <=* p * e * s * inizia con un p , * xy * deve essere costituito solo da "A". Perciò:

* x =a j per alcuni j> =0

* y =a k per alcuni k> 0 (perché | y |> 0)

* z =a p-j-k B p

5. Scegli i =0. Quindi xy i z =xz =a j A p-j-k B p =a p-k B p . Da K> 0, P - K p-k B p * non * in L.

6. Contradiction! Il lemma di pompaggio dice che per tutto io, xy i Z deve essere in L. Abbiamo trovato una divisione e un valore di I per il quale non lo è.

7. Pertanto, L non è regolare.

Considerazioni chiave e migliori pratiche:

* Scegli il metodo giusto: Il metodo migliore dipende dalla lingua.

* Per lingue semplici, la costruzione di un DFA/NFA o un'espressione regolare è spesso il più semplice.

* Per le lingue costruite da altre lingue regolari che utilizzano operazioni standard, utilizzare le proprietà di chiusura.

*Per le lingue sospettate di essere *non regolare *, utilizzare il lemma di pompaggio o il teorema di Myhill-nnerode.

* chiarezza e rigore: Quando si prova una lingua è regolare, definisci chiaramente l'automa/espressione regolare e spiega perché accetta * tutte * stringhe nella lingua e * solo * quelle stringhe. In altre parole, prova entrambe le direzioni dell'implicazione. Una descrizione vaga non è sufficiente.

* minimizzazione: Se costruisci un DFA, è utile (ma non richiesto) per minimizzarlo. Un DFA minimizzato è unico per una determinata lingua.

* Pratica: Lavorare attraverso molti esempi è il modo migliore per comprendere questi concetti e sviluppare l'intuizione necessaria per applicarli in modo efficace.

In sintesi, dimostrare che un linguaggio è regolare in genere comporta la dimostrazione della sua equivalenza a una definizione formale di regolarità:costruendo direttamente una macchina (FA) o un modello (espressione regolare) che lo riconosce o mostrando che è costruita da componenti regolari usando operazioni note che preservano la regolarità. Il lemma di pompaggio, al contrario, viene utilizzato per confutare la regolarità.

• Come si può dimostrare che una lingua è senza contesto? 
• Come si può usare il lemma di pompaggio per dimostrare che una lingua non è senza contesto?