Linguaggi formali

Un linguaggio formale è una sorta di generalizzazione del concetto di linguaggio a cui siamo abituati nella vita di tutti i giorni.

Concetti di base

Per cominciare, possiamo immaginare un linguaggio formale come un linguaggio comune, per esempio l’italiano. Di che cosa è fatto un linguaggio così? È fatto di parole, che poi combiniamo in frasi. Le frasi non ci interesseranno, ci interesseranno soltanto le parole. Di che cosa sono fatte le parole? Delle lettere dell’alfabeto. Cominceremo quindi dall’alfabeto.

Un alfabeto è un qualsiasi insieme non vuoto. Gli elementi dell’alfabeto si chiamano simboli. Se parliamo dell’italiano, sarà il normale alfabeto italiano con le lettere minuscole e maiuscole, più le varianti con gli accenti. Se invece non volessimo descrivere l’italiano, ma per esempio i numeri, nell’alfabeto avremmo tutte e dieci le cifre. L’alfabeto si indica spesso con il simbolo Σ.

Per parola, o anche stringa, intendiamo una successione finita di simboli di un alfabeto Σ. Se abbiamo per esempio l’alfabeto Σ= {a,b,c,d,e,…, z}, una parola è per esempio la successione «ciao» o «cane», ma non «perché» (non abbiamo la lettera «é»), «Marco» (non abbiamo la lettera «M») o «buon giorno» (non abbiamo lo spazio). Per lunghezza di una parola intendiamo il numero di simboli di cui la parola è composta.

Concatenazione di parole: date due parole a = a₁a₂… a_n e b = b₁b₂… b_m, la concatenazione delle parole dà la parola ab = a₁a₂… a_nb₁b₂… b_m. Esempio: concatenando le parole «ciao» e «cane» otteniamo la parola «ciaocane». La concatenazione si indica con un cerchietto, cioè a ∘ b, oppure non si indica in alcun modo e si scrivono semplicemente le parole una dopo l’altra, senza un simbolo speciale per la concatenazione.

La parola vuota si indica con ε ed è la parola che ha lunghezza zero. Se concateniamo la parola a = a₁… a_n con la parola vuota ε, otteniamo di nuovo la parola a. Vale cioè a ∘ ε = a.

La chiusura dell’alfabeto Σ è l’insieme di tutte le parole che siamo in grado di formare con l’alfabeto Σ, compresa la parola vuota. La chiusura si indica con Σ^∗. Se abbiamo l’alfabeto binario Σ= {0, 1}, allora vale

$${\mathrm{\Sigma }}^{\ast }=\{\epsilon ,0,1,00,01,10,11,000,001,\dots \}$$

A volte usiamo anche la chiusura positiva dell’alfabeto, che è ancora l’insieme di tutte le parole che siamo in grado di formare con l’alfabeto, tranne la parola vuota. La chiusura positiva si indica con Σ⁺ e vale Σ⁺ = Σ^∗ ∖ {ε}.

Esempi di alfabeti

• Torniamo all’esempio dell’italiano. Ogni parola italiana si trova nella chiusura di un alfabeto che contiene le lettere minuscole e maiuscole e le varianti con i segni diacritici (più forse anche l’apostrofo «’» e il trattino «-»). Se a questo alfabeto aggiungiamo anche lo spazio e i segni di punteggiatura (virgola, punto, punto esclamativo, punto interrogativo, …), con la chiusura otteniamo tutte le frasi che siamo in grado di formare in lingua italiana. Naturalmente di questa chiusura faranno parte anche frasi del tipo «sadflsf kasdf kagrjewòiàùèkr kf fkjbsjbgvbadfgsa!!!:??: ::!?:?:sdf», che restano comunque più sensate di tanti commenti che si leggono in rete.

• Se il nostro alfabeto contiene tutte le cifre Σ= {0, 1, …, 9}, nella chiusura ci saranno tutti i numeri naturali – e anche qualcosa in più. Ci saranno infatti anche numeri che iniziano con lo zero, per esempio 00054, e in più ci sarà la parola vuota, che ovviamente non è un numero.

• L’alfabeto deve essere non vuoto, quindi l’alfabeto più piccolo ha almeno un simbolo. Per esempio, per l’alfabeto Σ= {!} otterremmo la chiusura Σ^∗ = {ε, !, !!, !!!, !!!!, …}, cioè un insieme di parole, in cui per ogni n ∈ ℕ esiste una parola con n punti esclamativi e nella chiusura non ci sarà nessun’altra parola.

• Sia Σ= {qw,c}. È un alfabeto molto strano, perché contiene la parola qw. Questa notazione di solito non si usa, perché è confusa e bizzarra, ma possiamo immaginarla così: incolliamo le lettere «q» e «w» in modo che formino un unico carattere. Allora possiamo vedere la parola «qw» come il simbolo «qw». Se con questo simbolo formassimo la parola «qwcqw», questa parola avrebbe lunghezza tre: sarebbe composta dai simboli «qw», «c» e «qw». Alfabeti di questo tipo non capitano molto spesso, ma esistono situazioni in cui abbiamo bisogno di simboli composti da più simboli.

Linguaggio formale

Un linguaggio (formale) su un alfabeto Σ è un qualsiasi sottoinsieme di Σ^∗. Per un linguaggio L sull’alfabeto Σ vale quindi L ⊆ Σ^∗. Esempi di linguaggi:

• Nella parte precedente abbiamo definito l’alfabeto delle cifre Σ= {0, 1, …, 9}. La chiusura è l’insieme di tutte le parole formate soltanto da cifre. Se aggiungiamo la regola che la parola non può iniziare con zero e non può essere vuota, otteniamo l’insieme dei numeri naturali diversi da zero ℕ^*. Vale la relazione ℕ^* ⊆ Σ^∗, quindi ℕ^* è un linguaggio sull’alfabeto Σ.

• All’insieme di cifre precedente possiamo aggiungere anche il segno meno «-», quindi Σ= {0, 1, …, 9, −}. La chiusura è l’insieme di tutte le parole composte da cifre o dal segno meno. Questo però significa che nella chiusura ci sono anche parole come «12-84-», «1-5-8» o «-». Il linguaggio dei numeri interi relativi ℤ si ottiene aggiungendo tre regole:

  • Il segno meno non compare affatto nella parola oppure compare all’inizio della parola.
  • La prima cifra della parola non può essere zero, tranne nella parola «0».
  • Ogni parola deve contenere almeno una cifra.

  Questo insieme descrive l’insieme dei numeri interi relativi ed è un sottoinsieme dell’insieme Σ^∗ – è quindi un linguaggio sull’alfabeto Σ.

• Sia Σ= {0, 1}. La chiusura è quindi l’insieme di tutte le parole composte da zeri e uni. Possiamo definire un linguaggio L su questo alfabeto, per esempio, come l’insieme di tutte le parole che hanno esattamente tre uni. Possiamo anche essere più creativi e dire che il linguaggio L è l’insieme di tutte le parole che rappresentano un formato valido di un file docx (quello che esce da Word).

• Restiamo all’alfabeto binario Σ= {0, 1}. Ogni stringa di caratteri (i normali caratteri della tastiera) può essere convertita in forma binaria, cioè in zeri e uni, e poi di nuovo indietro, per esempio con la tabella ASCII (o più precisamente: la tabella ASCII converte i caratteri in numeri e i numeri dal sistema decimale si possono convertire in numeri del sistema binario). Possiamo così definire il linguaggio di tutte le parole che corrispondono a un indirizzo email valido, e sarà ancora un linguaggio sull’alfabeto binario.

Concatenazione di linguaggi: possiamo concatenare anche i linguaggi. La definizione è simile a quella del prodotto cartesiano di insiemi. Siano dati due linguaggi L₁ e L₂. La loro concatenazione L₁ ∘ L₂ è un nuovo linguaggio, che definiamo così:

$$L_1\circ L_2=\{w_1\circ w_2\mid w_1\in L_1,w_2\in L_2\}$$

Cioè prendiamo tutte le parole del linguaggio L₁ e le concateniamo con tutte le parole del linguaggio L₂. Esempio: siano

$$\begin{array}{rcl}{L}_1& =& \{0,1\}\\ L_2& =& \{a,b,ciao\}\end{array}$$

Allora vale:

$$\begin{array}{rcl}{L}_1\circ L_2& =& \{0a,0b,0ciao,1a,1b,1ciao\}\\ L_2\circ L_1& =& \{a0,a1,b0,b1,ciao0,ciao1\}\\ L_1\circ L_1& =& \{00,01,10,11\}\end{array}$$

Finora per descrivere i linguaggi abbiamo usato il linguaggio comune: abbiamo semplicemente descritto a parole come deve essere fatto il linguaggio. Questo però è molto poco pratico, perciò si introducono modi più formali per definire un linguaggio. Il primo di questi è la grammatica.