Come puoi usare il lemma di pompaggio per dimostrare che una lingua non è regolare?

Il lemma di pompaggio per le lingue regolari è uno strumento potente per dimostrare che una lingua non è * regolare. Funziona per contraddizione:si assume che la lingua * sia * regolare, quindi mostra che questa ipotesi porta a una contraddizione del lemma stesso. Ecco come funziona:

1. L'istruzione Lemma di pompaggio:

Il lemma di pompaggio afferma che per qualsiasi lingua normale L, esiste una lunghezza di pompaggio P tale che qualsiasi stringa w in l con lunghezza | w | ≥ p può essere diviso in tre sottostringhe, W =XYZ, che soddisfano le seguenti condizioni:

* | xy | ≤ P: La lunghezza della concatenazione di X e Y è inferiore o uguale a p.

* | y |> 0: La sottostringa Y non è vuota.

* Per tutti i ≥ 0, xy i z ∈ L: Pompare y zero o più volte (incluso la rimozione interamente quando i =0) si traduce in una stringa che è ancora nella lingua L.

2. Strategia di prova:

Per dimostrare che una lingua L non è regolare usando il lemma di pompaggio, segui questi passaggi:

* Supponiamo che l sia regolare: Inizia assumendo, per motivi di contraddizione, che L è una lingua normale.

* Scegli una lunghezza di pompaggio P: Il lemma di pompaggio garantisce l'esistenza di una lunghezza di pompaggio P; Non è necessario trovare il suo valore effettivo, solo riferirlo come "P".

* Scegli una stringa w ∈ L tale che | w | ≥ P: Seleziona attentamente una stringa W dalla lingua L la cui lunghezza è almeno p. La scelta di W è cruciale; Deve permetterti di creare una contraddizione nel passaggio successivo. Ciò comporta spesso stringhe con una struttura specifica relativa alla definizione della lingua.

* Mostra che nessuna decomposizione W =XYZ soddisfa le condizioni del lemma di pompaggio: Questo è il cuore della prova. Per * qualsiasi * possibile decomposizione di w in xyz soddisfacente | xy | ≤ p e | y |> 0, devi dimostrare che esiste alcuni i ≥ 0 in modo tale che xy i Z ∉ L. Ciò significa che il pompaggio y viola la definizione della lingua L. Spesso, lo dimostri dimostrando che il pompaggio y lo farà:

* Introduci uno squilibrio: Cambia il numero di occorrenze di qualche simbolo, violando un vincolo di conteggio in L.

* Crea una struttura non valida: Rompere il modello o la struttura richiesto dalla definizione di L.

* Introdurre una sottostringa non valida: Crea una sottostringa che non appartiene alla lingua.

* Concludi che L non è regolare: Dal momento che hai dimostrato che non può esistere tale decomposizione per la stringa scelta W, questo contraddice il lemma di pompaggio. Pertanto, il presupposto iniziale che L sia regolare deve essere falso e che L non è regolare.

Esempio:dimostrare {a n B n | n ≥ 0} non è regolare:

Let l ={a n B n | n ≥ 0}.

1. Supponiamo che l sia regolare.

2. Scegli P: Lascia che P sia la lunghezza di pompaggio.

3. Scegli W: Let w =a p B p . Chiaramente, w ∈ L e | W | ≥ p.

4. Non mostrare la decomposizione soddisfa le condizioni: Consideriamo qualsiasi decomposizione w =xyz tale che | xy | ≤ p e | y |> 0. Da allora | xy | ≤ p, y deve consistere * solo * di A (perché y è una sottostringa dai primi caratteri P). Quindi, y =a k Per un po 'di k> 0. Ora, pompa y zero volte:xy 0 z =a p-k B p . Questa stringa non è in L perché il numero di A e B è diverso. Questo contraddice il lemma di pompaggio.

5. Concludi: Dal momento che abbiamo raggiunto una contraddizione, la nostra ipotesi che L sia regolare deve essere falsa. Pertanto, l ={a n B n | n ≥ 0} non è una lingua normale.

La chiave è scegliere attentamente la stringa `w` e analizzare abilmente tutte le possibili decomposizioni` xyz` per mostrare che il pompaggio `y` porta sempre a una stringa al di fuori della lingua. Più è complessa il linguaggio, più intricata è la scelta di `w` e l'analisi.

Come puoi usare il lemma di pompaggio per dimostrare che una lingua non è regolare?

Informazioni correlate

Articoli consigliati