Teoria dei linguaggi formali

Premessa

Ciao! Se è la prima volta che capiti su questo sito, ti consiglio di consultare la pagina principale di questo Giardino Digitale per scoprire meglio cos’è e come navigarlo.

Lo stato di questa nota è al momento: 🟡 Incompleta.

---

Quando pensiamo alla parola linguaggio, pensiamo normalmente a qualcosa che serve agli esseri umani per comunicare: l’italiano, l’inglese o la lingua dei segni. Un linguaggio è quindi un sistema che ci permette di costruire espressioni e di attribuire loro un significato.

Una lingua naturale, ossia una di quelle usate nella vita di tutti i giorni (come l’italiano), è estremamente complessa: non comprende soltanto un insieme di parole, ma anche regole grammaticali, eccezioni, ambiguità, contesto, significati impliciti e moltissimi altri fenomeni.

Per esempio, una persona capisce immediatamente che

Il gatto mangia il topo.

è una frase grammaticalmente ben formata, mentre

Gatto il topo mangia il.

non lo è.

Un essere umano può leggere una frase e utilizzare la propria conoscenza linguistica per stabilire se abbia senso. Un computer, invece, non possiede intuitivamente il concetto di “frase corretta”. Se vogliamo che possa elaborare un linguaggio, dobbiamo fornirgli una descrizione precisa e non ambigua delle sue regole, in modo che sia possibile stabilire meccanicamente quali espressioni sono ammesse e quali no.

È proprio da questa idea che nasce la teoria dei linguaggi formali, in cui il termine formale indica qualcosa che è stabilito da regole oggettive e ben chiare, non soggette a possibili interpretazioni come nel caso dei linguaggi naturali.

Definizione: teoria dei linguaggi formali

La teoria dei linguaggi formali è un ramo della matematica applicata che studia i linguaggi formali e le loro proprietà, utili in logica, informatica e linguistica.

1 - Introduzione ai linguaggi formali

Così come per i linguaggi naturali alla base di tutto ci sono le lettere dell’alfabeto con cui costruiamo le parole, anche i linguaggi formali hanno alla propria base i simboli di un alfabeto con cui possiamo costruire stringhe.

Partiamo quindi da questi concetti fondamentali per arrivare pian piano alla definizione di linguaggio formale.

1.1 - Simboli e alfabeti

Definizione: simbolo

Un simbolo (o carattere) è un oggetto matematico considerato come un’unità indivisibile all’interno di un linguaggio formale.

Esempi di simboli

Un simbolo può essere qualsiasi cosa vogliamo: i simboli più intuibili sono per esempio le lettere minuscole e maiuscole dell’alfabeto latino $\text{a},\text{b},\dots ,\text{z},\text{A},\text{B},\dots ,\text{Z}$ o le cifre decimali $0,1,\dots ,9$.

I simboli però possono essere anche altri tipi di caratteri, come il trattino basso $\text{\_}$ o anche figure geometriche come $△$ e $\square$ e, perché no, anche intere parole stesse possono essere considerate come simboli, per esempio le parole chiave $\text{if}$ e $\mathtt{while}$.

Definizione: alfabeto

Un alfabeto, denotato solitamente con $\Sigma$, è un insieme finito e non vuoto di simboli.

Esempi di alfabeti

Ecco un po’ di esempi di alfabeti:

• ${\Sigma }_1=\{0,1\}$ è l’alfabeto delle cifre binarie, i cui unici simboli sono $0$ e $1$.
• ${\Sigma }_2=\{0,1,\dots ,9\}$ è l’alfabeto delle cifre decimali.
• ${\Sigma }_3=\{\text{a},\text{b},\dots ,\text{z},\text{A},\text{B},\dots ,\text{Z}\}$ è l’alfabeto latino.

Ricordiamo che gli alfabeti sono a tutti gli effetti degli insiemi, quindi possiamo farci delle operazioni, come per esempio l’unione. Abbiamo quindi che

$$\begin{array}{rl}{\Sigma }_4& ={\Sigma }_2\cup \{\text{ , }\}\\ & =\{0,1,\dots ,9\}\cup \{\text{ , }\}\end{array}$$

è l’alfabeto che possiamo usare per rappresentare i numeri con la virgola, oppure

$$\begin{array}{rl}{\Sigma }_5& ={\Sigma }_2\cup {\Sigma }_3\cup \{\_\}\end{array}$$

è l’alfabeto che possiamo usare per gli identificatori in C.

1.2 - Stringhe

Gli alfabeti possono essere usati per creare stringhe.

Definizione: stringa

Una stringa (o parola o frase) su un alfabeto $\Sigma$ è una sequenza finita di simboli in $\Sigma$.

Una stringa particolare è quella vuota.

Definizione: stringa vuota

La stringa vuota, solitamente denotata con $\epsilon$, è la stringa composta da zero simboli.

1.2.1 - Operazioni e nozioni sulle stringhe

Definizione: stringhe uguali

Due stringhe si dicono uguali se e solo se sono composte dagli stessi simboli nello stesso ordine.

Esempio di stringhe non uguali

Per esempio, le stringhe $\text{caos}$ e $\text{caso}$ non sono uguali perché, anche se composte dagli stessi simboli, essi non compaiono nello stesso ordine.

Definizione: lunghezza di una stringa

Data una stringa $u$, la sua lunghezza $|u|$ è il numero di simboli di cui è costituita.

Esempi di lunghezze di stringhe

Abbiamo per esempio che la stringa $\text{aab}$ ha lunghezza $|\text{aab}|=3$, mentre la stringa vuota $\epsilon$ ha lunghezza $|\epsilon |=0$.

Definizione: concatenazione di due stringhe

Date due stringhe $u$ e $v$, la loro concatenazione $uv$ è la stringa ottenuta giustapponendo i simboli di $u$ seguiti dai simboli di $v$.

Esempio di concatenazione di stringhe

Date le stringhe $u=\text{po}$ e $v=\text{sta}$, la loro concatenazione $uv$ è $\text{posta}$.

Proprietà: neutralità della concatenazione rispetto alla stringa vuota

La stringa vuota $\epsilon$ è l’elemento neutro della concatenazione: infatti, presa una qualsiasi stringa $u$, la loro concatenazione $u\epsilon$ o $\epsilon u$ produce sempre $u$.

Proprietà: associatività della concatenazione

La concatenazione è associativa, cioè date tre stringhe $u$, $v$ e $w$ vale

$$u(vw)=(uv)w$$

Osservazione: non commutatività della concatenazione

La concatenazione non è commutativa, infatti date due stringhe $u$ e $v$ abbiamo che genericamente

$$uv\ne vu$$

eccetto nel caso in cui almeno una delle due è la stringa vuota $\epsilon$ (perché è l’elemento neutro della concatenazione) o in cui le due stringhe sono uguali.

Definizione: prefisso di una stringa

Date due stringhe $u$ e $w$, diciamo che $u$ è un prefisso di $w$ se esiste una terza stringa $v$ tale che $w=uv$.

Definizione: suffisso di una stringa

Date due stringhe $u$ e $w$, diciamo che $u$ è un suffisso di $w$ se esiste una terza stringa $v$ tale che $w=vu$.

Esempio di prefisso e suffisso di una stringa

Date le stringhe $u=\text{posta}$ e $w=\text{postazione}$, abbiamo che $u$ è un prefisso di $w$ perché esiste la stringa $v=\text{zione}$ tale che $uv=w=\text{postazione}$.

Allo stesso modo, date le stringhe $u=\text{vero}$ e $w=\text{papavero}$, abbiamo che $u$ è un suffisso di $w$ perché esiste la stringa $v=\text{vero}$ tale che $vu=w=\text{papavero}$.

Osservazione: una stringa è prefisso e suffisso di se stessa

Data una stringa $u$, essa è contemporaneamente sia prefisso che suffisso di se stessa perché esiste la stringa vuota $\epsilon$ per cui $u\epsilon =u$ (nel caso del prefisso) e $\epsilon u=u$ (nel caso del suffisso).

Definizione: inversa di una stringa

Data una stringa $u=a_1{a}_2\dots a_n$, la sua inversa $u^R$ è la stringa ottenuta invertendo l’ordine dei simboli $a_1,a_2,\dots ,a_n$ di $u$:

$$u^R=a_n\dots a_2{a}_1$$

Esempio di inversa di una stringa

Data la stringa $a=\text{casa}$, la sua inversa è $a^R=\text{asac}$.

Definizione: stringa palindroma

Una stringa $u$ è palindroma se è uguale alla sua inversa $u^R$.

Esempi di stringhe palindrome

Un esempio di stringa palindroma è $u=\text{radar}$, la cui inversa $u^R$ è sempre $\text{radar}$. Anche la stringa vuota $\epsilon$ è considerata palindroma.

Definizione: potenza $n$-esima di una stringa

Data una stringa $u$, la sua potenza $n$-esima $u^n$ (con $n\in \mathbb{N}$) è la stringa ottenuta concatenando $u$ per $n$ volte:

$$u^n=\underset{n\text{ volte}}{\underbrace{uu\dots u}}=\{\begin{array}{ll}\epsilon & \text{se }n=0\\ u^{n-1}u& \text{se }n>0\end{array}$$

^definizione-potenza-n-esima-di-una-stringa

1.3 - Linguaggi formali

Ora possiamo finalmente definire cos’è un linguaggio formale.

Definizione: linguaggio formale

Un linguaggio formale (o più semplicemente linguaggio) $L$ su un alfabeto $\Sigma$ è un qualunque insieme di stringhe su $\Sigma$.

Esempi di linguaggi formali

Dato l’alfabeto $\Sigma =\{0,1\}$ delle cifre binarie, un possibile linguaggio formale $L$ su $\Sigma$ è

$$\{\epsilon ,1,01,100,1010111,\dots \}$$

Un altro possibile linguaggio è $L=\Sigma$, formato unicamente dai simboli dell’alfabeto.

Notazione: rappresentazione per caratteristica di un linguaggio

Esattamente come avviene per gli insiemi, anche i linguaggi possono essere rappresentati per caratteristica: per esempio,

$$\{{\text{a}}^{2n+1}\mid n\in \mathbb{N}\}$$

indica il linguaggio composto dalle stringhe di $\text{a}$ di lunghezza dispari, oppure

$$\{{\text{a}}^m{\text{b}}^n\mid m,n\in \mathbb{N}\}$$

indica il linguaggio delle stringhe composte da un numero arbitrario di $\text{a}$ seguite da un numero arbitrario di $\text{b}$.

Definizione: linguaggio vuoto

Il linguaggio vuoto $\varnothing$ è un linguaggio contenente zero stringhe ed è quindi un insieme vuoto.

Attenzione: linguaggio vuoto diverso da linguaggio con stringa vuota

Il linguaggio vuoto, corrispondente a un insieme vuoto $\varnothing$, e un linguaggio $L$ composto dalla sola stringa vuota non sono la stessa cosa, perché mentre il primo non ha elementi, il secondo ha un solo elemento che è $\epsilon$:

$$\varnothing \ne \{\epsilon \}$$

1.3.1 - Operazioni su linguaggi

Osservazione: operazioni insiemistiche sui linguaggi

Dal momento che i linguaggi sono insiemi, anche su di essi possono essere applicate le operazioni insiemistiche dell’unione $\cup$, intersezione $\cap$ e differenza $\setminus$.

Definizione: potenza $n$-esima di un alfabeto

Dato un alfabeto $\Sigma$, la sua potenza $n$-esima ${\Sigma }^n$ (con $n\in \mathbb{N}$) è il linguaggio costituito da tutte le stringhe su $\Sigma$ di lunghezza $n$:

$${\Sigma }^n=\{a_1{a}_2\cdots a_n\mid \forall i\in \{1,\dots ,n\}.(a_i\in \Sigma )\}$$

In particolare, ${\Sigma }^0=\epsilon$.

Esempio di potenza $n$-esima di un alfabeto

Dato l’alfabeto $\Sigma =\{\text{a},\text{b}\}$, la sua potenza seconda ${\Sigma }^2$ è il linguaggio

$${\Sigma }^2=\{\text{aa},\text{ab},\text{ba},\text{bb}\}$$

Proposizione: cardinalità della potenza $n$-esima di un alfabeto

Dato un alfabeto finito $\Sigma$, con $|\Sigma \text{vDashm}$, e dato un $n\in \mathbb{N}$, la cardinalità della sua potenza $n$-esima ${\Sigma }^n$ è:

$$|{\Sigma }^n\models |\Sigma {|}^n=m^n$$

Dimostrazione: cardinalità della potenza $n$-esima di un alfabeto

Per definizione, ${\Sigma }^n$ è l’insieme di tutte le stringhe su $\Sigma$ di lunghezza $n$ formate da simboli appartenenti a $\Sigma$ e, quindi, per costruire una stringa di lunghezza $n$ è necessario scegliere un simbolo di $\Sigma$ per ciascuna delle $n$ posizioni della stringa.

Poiché $|\Sigma \text{vDashm}$ per ipotesi, per la prima posizione possiamo scegliere tra $m$ simboli dell’alfabeto, per la seconda posizione stessa cosa, e così via fino alla $n$-esima posizione. Per il principio fondamentale del conteggio, il numero totale di stringhe ottenibili è quindi:

$$\underset{n\text{ volte}}{\underbrace{m\cdot m\cdot \dots \cdot m}}=m^n$$

Pertanto:

$$|{\Sigma }^n{\text{vDashm}}^n=|\Sigma {|}^n$$

Per $n=0$, si ha ${\Sigma }^0=\epsilon$ e quindi:

$$|{\Sigma }^0\models 1=|\Sigma {|}^0$$

$■$

Definizione: chiusura di Kleene su un alfabeto

Dato un alfabeto $\Sigma$, la sua chiusura di Kleene ${\Sigma }^{\ast }$ è il linguaggio formato da tutte le stringhe su $\Sigma$, inclusa quella vuota $\epsilon$. Formalmente, è l’unione di tutte le potenze $n$-esime di $\Sigma$:

$${\Sigma }^{\ast }=\bigcup _{i\in \mathbb{N}}{\Sigma }^i$$

Esempio di chiusura di Kleene su un alfabeto

Dato l’alfabeto $\Sigma =\{\text{a},\text{b}\}$, la sua chiusura di Kleene ${\Sigma }^{\ast }$ è

$$\begin{array}{rl}{\Sigma }^{\ast }& =\bigcup _{i\in \mathbb{N}}{\Sigma }^i\\ & ={\Sigma }^0\cup {\Sigma }^1\cup {\Sigma }^2\cup {\Sigma }^3\cup \dots \\ & =\{\underset{{\Sigma }^0}{\underbrace{\epsilon }},\underset{{\Sigma }^1}{\underbrace{\text{a},\text{b}}},\underset{{\Sigma }^2}{\underbrace{\text{aa},\text{ab},\text{ba},\text{bb}}},\underset{\text{parte di }{\Sigma }^3}{\underbrace{\text{aaa},\text{aab},\text{aba},\text{abb},\text{baa}}},\dots \}\end{array}$$

Definizione: chiusura transitiva su un alfabeto

Dato un alfabeto $\Sigma$. la sua chiusura transitiva ${\Sigma }^{+}$ è il linguaggio formato da tutte le stringhe su $\Sigma$, eccetto quella vuota $\epsilon$. Formalmente, è l’unione di tutte le potenze $n$-esime di $\Sigma$ eccetto ${\Sigma }^0$:

$${\Sigma }^{+}=\bigcup _{i\in \mathbb{N}\setminus \{0\}}{\Sigma }^i$$

o, in alternativa,

$${\Sigma }^{+}={\Sigma }^{\ast }\setminus \{\epsilon \}$$

Esercizio sulle chiusure sugli alfabeti

Dato l’alfabeto $\Sigma =\{\text{a},\text{b},\text{c}\}$, elenca dieci stringhe del linguaggio

$$L={\Sigma }^{+}\setminus \{\text{b},\text{c}{\}}^{\ast }$$

Soluzione dell'esercizio sulle chiusure sugli alfabeti

Il linguaggio $L={\Sigma }^{+}\setminus \{\text{b},\text{c}{\}}^{\ast }$ è formato dalla differenza tra la chiusura transitiva $L_1={\Sigma }^{+}$ e la chiusura di Kleene $L_2=\{\text{b},\text{c}\}$.

In particolare, la chiusura transitiva $L_1={\Sigma }^{+}$ indica l’insieme di tutte le stringhe su $\Sigma$, eccetto quella vuota $\epsilon$, mentre la chiusura di Kleene $L_2=\{\text{b},\text{c}\}$ indica l’insieme di tutte le stringhe su $\{\text{b},\text{c}\}$ compresa quella vuota $\epsilon$.

Quindi, facendo la differenza tra $L_1={\Sigma }^{+}$ (cioè tutte le stringhe formate dai simboli $\text{a}$, $\text{b}$ o $\text{c}$) e $L_2=\{\text{b},\text{c}\}$ (cioè tutte le stringhe formate dai simboli $\text{b}$ o $\text{c}$), otteniamo le stringhe che contengono il simbolo $\text{a}$ almeno una volta:

$$\begin{array}{rl}L& =L_1\setminus L_2\\ & ={\Sigma }^{+}\setminus \{\text{b},\text{c}{\}}^{\ast }\\ & =\{\text{a},\text{ba},\text{ac},\text{ccac},\text{bba},\text{aab},\text{aca},\text{baa},\text{bac},\text{cacca},\dots \}\end{array}$$

Ora possiamo “ri-definire” l’operazione insiemistica del complemento, applicando questo concetto ai linguaggi formali.

Definizione: complemento di un linguaggio

Dato un linguaggio $L$ su un alfabeto $\Sigma$, il suo complemento $\overline{L}$ è il linguaggio ottenuto dalla differenza tra la chiusura di Kleene ${\Sigma }^{\ast }$ e $L$ stesso:

$$\overline{L}={\Sigma }^{\ast }\setminus L$$

Definizione: concatenazione di due linguaggi

Dati due linguaggi $L_1$ e $L_2$, la loro concatenazione $L_1{L}_2$ è il linguaggio ottenuto concatenando ogni stringa $u\in L_1$ con ogni stringa $v\in L_2$:

$$L_1{L}_2=\{uv\mid u\in L_1\wedge v\in L_2\}$$

Esempio di concatenazione di due linguaggi

Dati i linguaggi $L_1=\{\text{ca},\text{pa}\}$ e $L_2=\{\text{sta},\text{ne}\}$, la loro concatenazione $L_1{L}_2$ è

$$L_1{L}_2=\{\text{casta},\text{pasta},\text{cane},\text{pane}\}$$

Proprietà: associatività della concatenazione di linguaggi

La concatenazione è associativa, cioè dati tre linguaggi $L_1$, $L_2$ e $L_3$ vale

$$L_1(L_2{L}_3)=(L_1{L}_2)L_3$$

Osservazione: non commutatività della concatenazione di linguaggi

La concatenazione non è commutativa, infatti dati due linguaggi $L_1$ e $L_2$ abbiamo che genericamente

$$L_1{L}_2\ne L_2{L}_1$$

eccetto in particolari casi, ad esempio quando almeno uno dei due è il linguaggio vuoto, oppure quando i due linguaggi coincidono.

Proprietà: assorbimento della concatenazione rispetto al linguaggio vuoto

Il linguaggio vuoto $\varnothing$ è un elemento assorbente della concatenazione: infatti, preso un qualsiasi linguaggio $L$, la loro concatenazione $L\varnothing$ o $\varnothing L$ produce sempre il linguaggio vuoto $\varnothing$.

Infatti, per la definizione di concatenazione, abbiamo che

$$L\varnothing =\{uv\mid u\in L\wedge v\in \varnothing \}$$

ma, poiché il linguaggio vuoto non contiene alcuna stringa, non esiste nessuna stringa $v$ tale che $v\in \varnothing$. Di conseguenza, non esistono stringhe concatenabili e l’insieme risultante non contiene alcun elemento: da qui l’insieme vuoto. Stesso discorso per $\varnothing L$.

Proprietà: neutralità della concatenazione rispetto al linguaggio contenente la stringa vuota

Il linguaggio $\{\epsilon \}$, costituito dalla sola stringa vuota, è l’elemento neutro della concatenazione dei linguaggi: infatti, preso un qualsiasi linguaggio $L$, la sua concatenazione con $\{\epsilon \}$, sia $L\{\epsilon \}$ sia $\{\epsilon \}L$, produce sempre $L$.

Esercizio 1 sulla concatenazione di linguaggi

Dato l’alfabeto $\Sigma =\{\text{a},\text{b},\text{c}\}$, elenca dieci stringhe del linguaggio

$$L=({\Sigma }^2\cup {\Sigma }^3)\{\text{a},\text{b}\}$$

Soluzione dell'esercizio 1 sulla concatenazione di linguaggi

Il linguaggio $L=({\Sigma }^2\cup {\Sigma }^3)\{\text{a},\text{b}\}$ è formato dalla concatenazione di $L_1={\Sigma }^2\cup {\Sigma }^3$ e $L_2=\{\text{a},\text{b}\}$.

Il linguaggio $L_1={\Sigma }^2\cup {\Sigma }^3$ indica l’unione delle potenze seconde e terze di $\Sigma$, ossia tutte le stringhe di lunghezza $2$ o $3$ su $\Sigma$, quindi

$$L_1=\{\text{ab},\text{bcc},\text{cb},\text{aaa},\text{ac}\dots \}$$

Concatenando queste cinque stringhe di $L_1$ con $L_2=\{\text{a},\text{b}\}$, otteniamo

$$\begin{array}{rl}L& =L_1{L}_2\\ & =\{\text{ab},\text{bcc},\text{cb},\text{aaa},\text{ac}\dots \}\{\text{a},\text{b}\}\\ & =\{\text{aba},\text{bcca},\text{cba},\text{aaaa},\text{aca},\text{abb},\text{bccb},\text{cbb},\text{aaab},\text{acb},\dots \}\end{array}$$

ed ecco dieci possibili stringhe di $L$.

Definizione: potenza $n$-esima di un linguaggio

Dato un linguaggio $L$, la sua potenza $n$-esima $L^n$ (con $n\in \mathbb{N}$) è il linguaggio ottenuto concatenando $L$ per $n$ volte:

$$L^n=\underset{n\text{ volte}}{\underbrace{LL\dots L}}=\{\begin{array}{ll}\{\epsilon \}& \text{se }n=0\\ L^{n-1}L& \text{se }n>0\end{array}$$

Esempio di potenza $n$-esima di un linguaggio

Dato il linguaggio $L=\{\text{sıˋ},\text{no}\}$, la sua potenza seconda $L^2$ è il linguaggio

$$\begin{array}{rl}{L}^2& =L{L}^1\\ & =LL{L}^0\\ & =\{\text{sıˋ},\text{no}\}\{\text{sıˋ},\text{no}\}\{\epsilon \}\\ & =\{\text{sıˋsıˋ},\text{sıˋno},\text{nosıˋ},\text{nono}\}\end{array}$$

2 - Approcci per la descrizione di linguaggi

Come abbiamo visto, possiamo descrivere un linguaggio formale attraverso le stringhe che lo compongono. Solitamente, ai fini dello studio, i linguaggi davvero interessanti sono quelli contenenti un numero infinito di stringhe, ma non è possibile descriverli semplicemente elencandole tutte (come per esempio fanno i vocabolari che elencano tutte le parole di una lingua).

Occorre quindi un approccio finito per descrivere un linguaggio infinito: potremmo per esempio trovare un modo meccanico per dire se una stringa è “accettabile” all’interno di un linguaggio o meno.

---

Fonti

• 🏫 Corso di Laurea in Informatica (L-31 R) presso l’Università di Torino:
  • Corso di Linguaggi Formali e Traduttori (INF0344), A.A. 2026-27 (pagina Moodle):
    • Prof. Jeremy James Sproston, slide del corso:
      • 1.3 - Linguaggi.