Breve introduzione

Una grammatica è un dispositivo per generare un insieme di frasi.
Un linguaggio è un insieme di frasi.
Un automa e' una macchina in grado di riconoscere un insieme di frasi.
I linguaggi piu' interessanti per le applicazioni informatiche sono quelli di tipo 3 o di tipo 2, secondo la classificazione del linguista americano Noam Chomsky (1956).

In questa pagina parleremo degli automi riconoscitori dei linguaggi di tipo 2. Questi automi sono denominati PDA (Push Down Automata) o  riconoscitori a pila (stack).
I PDA sono dotati di una pila che funge da memoria aggiuntiva e per questo si differenziano dagli automi a stati finiti (FA - Finite Automata) che possono riconoscere solo linguaggi di tipo 3.  Senza memoria un PDA non potrebbe realizzare le operazioni di confronto e quindi non potrebbe fare conti su due quantità diverse.

In altri termini mentre le grammatiche di tipo 3 posso generare stringhe composte da un numero qualunque di a e di b, es: aabbbbbbaaabb, esse non possono generare stringhe che hanno p.e. n lettere a seguite da n lettere b (in forma compatta anbn) oppure, generare le stringhe anb2n (stringhe in cui le b sono in numero doppio rispetto alle a). Diciamo che le grammatiche di tipo 3 non possono effettuare questo tipo di 'controllo' sulle occorrenze di a e di b. Vedremo come i PDA possono raggiungere questo obiettivo grazie alla memoria a pila. Questi automi che riconoscono linguaggi di tipo 2 (liberi dal contesto - context free) sono molto importanti perchè sono utilizzati per riconoscere la correttezza sintattica (analisi sintattica) dei linguaggi di programmazione e per realizzare i text-processors in genere.



Push Down Automata (PDA)

Esercizo svolto:
Costruire un automa per riconoscere il linguaggio: L = {stringhe in {a,b}+ contenenti una sottostringa palindrome di lunghezza pari, maggiore di due}
Una parola o frase si dice palindrome se, pur leggendola in senso inverso rimane identica. Esempi: Roma amor, anilina.  Quale sarà l'automa in grado di riconoscere le stringhe palindromi non banali? Dall'esempio notiamo che esiste una simmetria centrale, e quindi possiamo pensare che le stringhe palindromi siano generate da grammatiche di tipo 2.
Una chiave risolutiva del problema potrebbe essere quella di individuare un possibile "centro" della stringa palindrome. Essendo il primo obiettivo quello di trovare un centro, il nostro automa dovrà scorrere la stringa di a e di b e fermarsi nonappena legge due a o due b consecutive.

Avendo escluso dal nostro automa il riconoscimento di stringhe palindromi banali (a) o di lunghezza 2 (aa), il nostro automa dovra' analizzare anche i due caratteri che precedono o che seguono le due lettere ripetute. Se anche le due lettere adiacenti alle due uguali sono identiche il nostro automa riconoscera' una sottostringa palindrome non banale e potra' passare nello stato finale q2.


 
stato q0
stato q1
stato q2 (accettazione)
§ (qo,b, Z) = (qo, BZ) inizio
§ (qo,a, Z) = (qo, AZ) inizio
§ (qo,a, B) = (qo, AB) push A
§ (qo, b, A) = (qo, BA) push B
§ (qo, b, B) = (q1, e) 2 b => pop B 
§ (qo, a, A) = (q1, e) 2 a => pop A
§ (q1, a, Z) = (qo, AZ) pal. banale
§ (q1, b, Z) = (qo, BZ) pal. banale
§ (q1, b, A) = (qo, BA) pal. banale
§ (q1, a, B) = (qo, AB) pal. banale
§ (q1, b, B) = (q2, e) pal. lung. pari
§ (q1, a, A) = (q2, e) pal. lung. pari
§ (q2, a, B) = (q2, e) pop b
§ (q2, b, A) = (q2, e) pop a
§ (q2, e, Z) = (q2, e) pila vuota
Data la seguente stringa il nostro automa riconosce la sottostringa palindrome di lunghezza pari: abbbabaab.


Prossimo esercizio


Termini mancanti/suggerimenti ?

© Copyright 1997-2001 by Francesco Longo, flongo@dsi.unive.it

Homepage Dizionario Informatico