Linguaggi regolari

Oggi si va un po’ di più sulla teoria. Oh, prima o poi toccava farlo. Qui il link al post precedente.

Linguaggi

Chi di voi conosce Noam Chomsky? Si proprio lui, avete sentito bene: il vecchio anarchico americano, uno dei pochissimi rimasti. Una persona decisamente controcorrente, sempre pronto a dire la sua fuori dal coro, dai tempi in cui si oppose alla guerra in Vietnam, fino alla guerra del golfo e la guerra in Iraq con il suo attivismo pacifista, nonostante l’età. In effetti, non deve essere facile essere come lui in un paese come gli USA.

Ma che c’entra Noam Chomsky con l’informatica e con le espressioni regolari? Moltissimo a dire la verità. Infatti, il vero mestiere di Noam Chomsky è quello del ricercatore nel campo della linguistica, e uno dei padri ispiratori della disciplina della linguistica computazionale, una disciplina al confine tra l’informatica e la linguistica classica.

In particolare, Chomsky è l’inventore del concetto di grammatica generativa e della classificazione dei linguaggi formali. Cosè un linguaggio formale?

Si parte con un alfabeto definito come un insieme di simboli (ad esempio le lettere dell’alfabeto italiano o inglese, oppure il codice ASCII). L’importante è definire appunto l’insieme dei simboli.

Una parola è una sequenza di simboli. Ad esempio, se prendiamo l’alfabeto italiano, sono parole le seguenti abc, aaaa, informatica, parola, ecc. Basta prendere una sequenza di simboli, non importa se abbia o no “senso comune”. La sequenza potrebbe anche essere illimitata, ovvero contenere un numero a priori illimitato di simboli.

A questo punto un linguaggio L è un sottoinsieme delle possibili parole. Ad esempio, potrei definire un linguaggio L1 che contiene le parole “Giuseppe” e “aaa”. Non che un linguaggio così abbia senso, ma è per farvi capire la generalità della definizione. Un altro linguaggio potrebbe essere quello dei codici di una tastiera che permettono l’apertura di una porta. Ovvero, l’esempio visto negli scorsi post. Ad esempio, il linguaggio L2 di una fantomatica porta potrebbe contenere due parole soltanto, 12A45 e 22B48.

Oppure potrei dire che il linguaggio L3 contiene parole che cominciano per il simbolo a e successivamente sono formate da un numero da zero a illimitato di sequenze della coppia ab. Per esempio, aababab è una parola del linguaggio, così come a e aab, mentre la parola aaa non lo è.

Quindi i linguaggi possono contenere un numero finito di parole, oppure infinito. Nel primo caso basta elencarle tutte. Nel secondo caso, devo dare una regola di appartenenza.

Le regole di un linguaggio

Concentriamoci sul secondo caso: vogliamo definire un linguaggio dando delle regole. Possiamo farlo in due modi: generativo, oppure riconoscitivo.

Nel caso generativo, diamo delle regole per generare tutte le parole che appartengono al linguaggio: in pratica, dato l’alfabeto iniziale e le regole, possiamo creare la lista delle parole che compongono il linguaggio. Queste regole si chiamano grammatica. Si, proprio come la vostra vecchia grammatica di italiano che portavate a scuola tutti i giorni quando eravate dei pischelli. Naturalmente, in questo contesto, grammatica significa in realtà algoritmo o procedura per generare un elenco di parole.

Nel caso riconoscitivo, vogliamo risolvere in problema leggermente diverso: data una parola, vogliamo sapere se questa fa parte di un linguaggio. Naturalmente, ogni linguaggio avrà le sue regole. Salta fuori che un cosa come gli automi che abbiamo visto negli scorsi post sarebbero adatti ad implementare dei riconoscitori.

I due metodi sono uno il duale dell’altro: in particolare, una strategia per riconoscere se una data parola w appartiene o no al linguaggio potrebbe essere la seguente:

  • generare la lista di tutte le parole del linguaggio che hanno la stessa lunghezza di w;
  • vedere se w è presente nella lista.

Viceversa, se vogliamo generare tutte le parole di un linguaggio, si potrebbe:

  • generare tutte le possibili parole di lunghezza 1, 2, 3, … n,
  • e vedere quali di queste sono riconosciute dal riconoscitore.

E quindi, grammatica o riconoscitore, per noi pari sono. Più o meno.

Potenza espressiva

Ma non tutti i linguaggi sono ugualmente “facili”. In particolare, certi linguaggi sono più “semplici” e altri sono più difficili. Chomsky classificò i linguaggi in varie categorie, a seconda del tipo di algoritmo per generare/riconoscere il linguaggio. Ecco la tabella dal più “semplice” al più “complesso”.

Tipo Linguaggio Tipo di Automa
3 Linguaggi regolari Automi a stati finiti
2 Linguaggi liberi dal contesto Automi a pila
1 Linguaggi dipendenti dal contesto Automi lineari
0 Ricorsivo Decisore / Macchina di Turing

Avete visto cosa c’è in alto a destra? I nostri amici automi a stati finiti! Si, gli automi sono in grado di riconoscere la categoria di linguaggi più semplice che c’è. Invece nella casella in basso a destra c’è la famosa Macchina di Turing, la macchina calcolatrice più espressiva di tutte. Quindi, i linguaggi ricorsivi sono i più “difficili” di tutti.

Esempio

A questo punto bisogna fare un esempio. Prendiamo il linguaggio che avevo definito prima: una parola appartiene al linguaggio se c’è una a come primo simbolo seguita da una sequenza di un numero qualsiasi (anche 0) di coppie ab. Ecco l’automa che riconosce le parole di questo linguaggio:

automa-linguaggio.png

Figure 1: Automa a stati finiti per il linguaggio dell’esempio

Nel disegnare la figura, ho fatto l’assunzione che se uno stato riceve un simbolo per cui non ha un arco in uscita, allora si blocca con errore. Per esempio, se mentre siamo in S0 arriva una b, allora l’automa si blocca con un errore. In realtà avrei dovuto mettere un stato apposito, per esempio ERR in cui si finisce quando arriva un simbolo inaspettato, e aggiungere degli archi da ciascuno stato allo stato di errore. Ma il disegno si complica inutilmente, e allora molto spesso si utilizza questa scorciatoia.

L’automa in figura definisce il linguaggio in maniera esatta. Cioè, invece di scrivere la definizione del linguaggio a parole, descrivo l’automa, che sicuramente è più preciso di qualunque descrizione in italiano. In effetti, l’automa è un modo procedurale di definire il linguaggio.

E se volessi utilizzare una grammatica? Si scrive più o meno così:

\displaystyle  a(ab)^n

dove l’elevazione a n indica la ripetizione per un numero intero di volte dei simboli contenuti tra le parentesi tonde. Sembra quasi uguale a un’espressione regolare, vero? L’espressione sarebbe:

a(ab)*

dove l’asterisco significa “il precedente pattern può essere ripetuto un numero arbitrario di volte (anche zero volte)”.

Notate che il pattern è illimitato. In altre parole, non abbiamo messo un limite alla lunghezza delle parole del linguaggio. Il nostro linguaggio L contiene dunque un numero infinito di parole! Tuttavia, poiché il pattern con cui queste parole sono generate è molto semplice, altrettanto semplici sono la grammatica e l’automa che lo descrivono.

Quindi, la difficoltà di un linguaggio non ha niente a che vedere con il numero di parole che contiene, ma semmai con la complessità del pattern di riconoscimento. Nell’ultima puntata spiegherò perché un automa a stati finiti non è poi così potente, e cosa non può riconoscere.

Errata Corrige

Nello scorso post ho fatto un errore: nella figura ho messo una freccia da da S3 a S2 con etichetta “2”; in realtà, la freccia doveva essere da S3 a S4, sempre con etichetta “2”. Grazie a Stefano per la segnalazione, è molto gratificante avere lettori attenti che ti trovano i bachi! Grazie ancora.

Annunci
Post a comment or leave a trackback: Trackback URL.

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger hanno fatto clic su Mi Piace per questo: