Il Dizionario Informatico, © www.dizionarioinformatico.com

Linguaggi formali

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 a ⁿbⁿ) oppure, generare le stringhe aⁿb²ⁿ (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 q ₂.

stato q₀	stato q₁	stato q₂(accettazione)
§ (q_o,b, Z) = (q_o, BZ) inizio § (q_o,a, Z) = (q_o, AZ) inizio § (q_o,a, B) = (q_o, AB) push A § (q_o, b, A) = (q_o, BA) push B § (q_o, b, B) = (q₁, e) 2 b => pop B § (q_o, a, A) = (q₁, e) 2 a => pop A	§ (q₁, a, Z) = (q_o, AZ) pal. banale § (q₁, b, Z) = (q_o, BZ) pal. banale § (q₁, b, A) = (q_o, BA) pal. banale § (q₁, a, B) = (q_o, AB) pal. banale § (q₁, b, B) = (q₂, e) pal. lung. pari § (q₁, a, A) = (q₂, e) pal. lung. pari	§ (q₂, a, B) = (q₂, e) pop b § (q₂, b, A) = (q₂, e) pop a § (q₂, e, Z) = (q₂, e) pila vuota

Data la seguente stringa il nostro automa riconosce la sottostringa palindrome di lunghezza pari: abbbabaab.