Swappa :: Traduttori - Appunti del 2 aprile 2009

 Torna alla pagina di Traduttori

:: Traduttori - Appunti del 2 aprile 2009 ::

Proprietà dei linguaggi regolari

Come già abbiamo detto, i linguaggi regolari ci piacciono, per quanto poco espressivi, perché godono di diverse proprietà dimostrabili algoritmicamente. E queste proprietà possono anche essere usate per riconoscere un linguaggio regolare: se riesco a dimostrare che un linguaggio gode di proprietà che solo i linguaggi regolari possono avere, posso inferire che si tratti di un linguaggio regolare.

Il Pumping Lemma

Il Pumping Lemma viene usato per discernere i linguaggi regolari dai non regolari. Anzi, per essere più preciso, rappresenta una condizione necessaria ma non sufficiente per poter dire se un linguaggio sia regolare o meno.

Necessaria ma non sufficiente vuol dire che, se il Pumping Lemma viene dimostrato come falso per un linguaggio, allora sono sicuro che il linguaggio non sia regolare. Se invece il Pumping Lemma è vero per un linguaggio, allora non posso dire che cosa esso sia.

L'intuizione di base del Pumping Lemma è che i linguaggi regolari devono essere riconosciuti da un automa con memoria finita. Se dimostro che un linguaggio non è riconoscibile da un automa con memoria finita, allora so che quel linguaggio non è regolare.

Dimostrazione

A è un automa (Q, δ, q₀, F) definito su un alfabeto Σ, con n stati. L_A è il linguaggio regolare da esso riconosciuto.

Possiamo dire che ∀ w ∈ L, w = xyz, ovvero che ogni parola appartenente al linguaggio più essere scomposta in un prefisso x, in una parte centrale y e in una parte finale z.

Discutiamo un po' della lunghezza della mia stringa w. Abbiamo detto che il mio automa ha n stati. Se |w| =m e m > n, significa che il cammino che porta alla sua accettazione dovrà per forza fare un loop in almeno uno stato. Questo è il famoso "principio della piccionaia": se ho 10 piccioni, ma 8 cellette, per forza qualche piccione dovrà condividere la sua celletta con qualcun'altro.

Lo stato i-esimo sarà il primo degli stati su cui sarà eseguito il loop, e j l'ultimo del loop. Ecco perché prima ho diviso la stringa w in tre parti:

x = da a₁ ad a_i
y = da a_i+1 ad a_j
z = da a_j+1 ad a_m'

w = xyz = (a₁ ... a_i) (a_i+1 ... a_j) (a_j+1 ... a_m)

Questo significa che la stringa generica xy^kz sarà accettata, perché il parametro k mi dice giusto quanti giri di loop devo fare!

k = 0 => nessun loop
k = 1 => xyz
k > 2 => faccio k loop

Pertanto, xy^kz è accettata ∀k.

Quindi, se io prendo un linguaggio, e vedo che NON sono in grado di ricondurlo alla forma xy^kz, allora quel linguaggio non è regolare.

Posso anche dire qualcosa sulle cardinalità delle varie componenti:

|x| < n: se x è il minimo prefisso che mi porta nello stato i-esimo, allora la sua cardinalità deve essere < n, altrimenti non potrei nemmeno avere il loop
|xy| <= n, il che comprende il fatto che |z| può anche essere 0
|y| >= 1, e questo perché devo come minimo arrivare allo stato finale, e se |x| è minore di n, allora y deve essere maggiore o uguale ad 1.

Quindi, il Pumping Lemma in versione definitiva dice che:
dato un linguaggio regolare L;
una stringa z ∈ L, con |z| >= n;
allora
z è della forma xyz, con |x| < n e |y| >= 1.

Esempio

Prendiamo il linguaggio in cui il numero di 0 è pari al numero di 1. In termini concisi il linguaggio è definito come 0ⁿ1ⁿ.

Supponiamo che questo linguaggio sia regolare. Se è vero, allora il Pumping Lemma mi dice che è della forma w = xyz, con |x| < n e |y| >= 1. Se è falso, sicuramente il linguaggio non sarà regolare.

Prendiamo allora la stringa 00000011111 suddivisa così:

x = 00000
y = 0
z = 111111

La condizione |x| < n è soddisfatta, così come |y| >= 1. Parrebbe tutto ok. Ma allora posso anche dire che xy^kz è parimenti accettata dal linguaggio? NO, perché avrei uno 0 in più!

Notiamo che basta trovare 1 solo esempio negativo, per invalidare un teorema. In questo caso avremmo potuto dividere anche la stringa in questo modo:

x = 000000
y = 1
z = 11111

ma il risultato sarebbe stato lo stesso.

In generale possiamo anche dire che i linguaggi in cui si conta il numero di occorrenze, cioè in qui il numero di occorrenze dei vari caratteri è vincolato in modo relativo (a^mbⁿ, con m = n, m = n +1 etc...) non sono affatto regolari.

Altre proprietà

Appena le recupero dal libro le scrivo qui:)

Torna alla pagina di Traduttori