Linguaggio formale (matematica)

In matematica, logica, informatica e linguistica, per linguaggio formale si intende un insieme di stringhe di lunghezza finita costruite sopra un alfabeto finito, cioè sopra un insieme finito di oggetti tendenzialmente semplici che vengono chiamati caratteri, simboli o lettere.

In maniera formale, un linguaggio L è definito come $L \subseteq \Sigma^{*}$. Un linguaggio può essere di cardinalità finita, infinita o nulla. È importante notare che il linguaggio vuoto (denotato da $L = \emptyset$) differisce dal linguaggio composto esclusivamente dalla stringa muta (o parola vuota), denotata con e, $\epsilon$ o λ.

Ad esempio, dato l'alfabeto $\Sigma = \left \{ a, b \right \}$ alcuni possibili linguaggi su tale alfabeto sono:

• il linguaggio vuoto
• $L = \left \{ \epsilon \right \}$ (linguaggio costituito solamente dalla stringa vuota)
• $L^{\prime} = \left \{ ababba, aaabbbaaa, aaabbbabaababb \right \}$ (linguaggio finito)
• $L^{\prime\prime} = a^{*} b^{*}$ (linguaggio infinito definito da un'espressione regolare)
• $L^{\prime\prime\prime} = \Sigma^{*}$

In generale diremo che un modello formale che può riconoscere e generare tutte e sole le stringhe di un linguaggio formale agisce come una definizione di tale linguaggio. Secondo i due principali approcci alla definizione dei linguaggi formali, un modello si può concretizzare in una grammatica formale (approccio generativo) o in un automa (approccio riconoscitivo).

Definizione di un linguaggio formale

Un linguaggio formale può essere definito in una grande varietà di modi:

• l'insieme delle stringhe derivate da una grammatica generativa
• l'insieme delle stringhe fornite da un'espressione regolare
• l'insieme delle stringhe accettata da un automa
• le domande a risposta affermativa, nell'ambito di un problema di decisione, la cui risposta è di tipo binario (sì/no o vero/falso)

Esempi di linguaggi formali

Sebbene siano stati definiti sopra alcuni esempi di linguaggi formali, è possibile esprimere alcuni linguaggi formali su Σ nel seguente modo:

• il linguaggio di tutte le stringhe che contengono lo stesso numero di a e di b;
• l'insieme di tutte le parole su Σ o l'insieme vuoto;
• l'insieme delle stringhe della forma aⁿ con n numero primo;
• l'insieme dei programmi in un dato linguaggio di programmazione che si dimostrano sintatticamente corretti;
• l'insieme degli input che causano l'arresto di una determinata macchina di Turing

Operazioni sui linguaggi formali

È possibile definire alcune operazioni unarie o binarie per generare un nuovo linguaggio a partire da lunguaggi dati. Siano L₁ ed L₂ due linguaggi su un dato alfabeto.

• $L = L_1 \circ L_2$ è la concatenazione o giustapposizione dei due linguaggi. Consiste nell'insieme di tutte le stringhe vw tali che $v \in L_1$ e $w \in L_2$.
• $L = L_1 \cap L_2$ è l'intersezione di L₁ ed L₂. Consiste nell'insieme di tutte le stringhe $w / w \in L_1 \and w \in L_2$, ovvero tutte le stringhe contenute sia in L₁ che in L₂.
• $L = L_1 \cup L_2$ è l'unione di L₁ ed L₂. Consiste nell'insieme di tutte le stringhe $w / w \in L_1 \or w \in L_2$, ovvero tutte le stringhe che appartengono ad almeno uno dei due linguaggi.
• $L = \bar{L}_1$ è il complemento del linguaggio L₁. Consiste in tutte le stringhe $w \in \Sigma^{*} \setminus L_1$, ovvero tutte stringhe sull'alfabeto Σ che non sono contenute in L₁.
• $L = L_1 \backslash L_2$ è il quoziente destro di L₁ da L₂. Consiste in tutte le stringhe v per le quali esiste una stringa w in L₂ tale che $vw \in L_1$.
• $L = L_1^{*}\,$ è la star di Kleene. Consiste nel linguaggio $\bigcup_{n \in \N} L_1^{n}$, ovvero tutte le stringhe della forma $w_1 w_2 \cdots w_n$ tali che $w_i / w_i \in L_1 \and 0 \le i \le n$. Poiché $L_1^{0} = { \epsilon }$ si ha che la stringa muta $\epsilon \in L$.
• $L = L_1^{R}\,$ è il riflesso. Se $w = a_1 a_2 \cdots a_n$ e $w^{R} = a_n a_{n-1} \cdots a_1$, il linguaggio L contiene tutte le stringhe $w_{R} / w \in L_1$, ovvero tutte le stringhe riflesse di L₁.
• Il mescolamento o shuffle di L₁ ed L₂ consiste di tutte le stringhe che si possono scrivere nella forma $v_1 w_1 v_2 w_2 \cdots v_n w_n$ tali che $n \ge 1 \and \left \{ v_1 \cdots v_n \right \} \in L_1 and \left \{ w_1 \cdots w_n \right \} in L_2$.

Uno dei problemi più comuni legati ai linguaggi formali riguarda il membership problem. Data un stringa w ed un linguaggio L, verificare se $w \in L$ è un problema che coinvolge sia la teoria della calcolabilità che la teoria della complessità.

Voci correlate

• Stringa (formale)
• Grammatica formale

Bibliografia

• Formal languages in Encyclopedia of Computer Science (in inglese), Hoboken, Wiley, 2003.
• John E. Hopcroft; Rajeev Motwani; Jeffrey D. Ullman, Languages in Introduction to Automata Theory, Languages, and Computation (in inglese), Addison Wesley, 15 luglio 2006. 978-0321462251

Portale Informatica: accedi alle voci di Wikipedia che trattano di Informatica

Teoria degli automi: linguaggi formali e grammatiche formali
Gerarchia di Chomsky	Grammatica	Linguaggio	Automa minimo
Tipo-0	(illimitato)	Ricorsivamente enumerabile	Macchina di Turing
	(illimitato)	Ricorsivo	Decider
Tipo-1	Dipendente dal contesto	Dipendente dal contesto	Automa lineare
Tipo-2	Libera dal contesto	Libero dal contesto	Automa a pila ND
Tipo-3	Regolare	Regolare	A stati finiti
Ciascuna categoria di linguaggio o grammatica è un sottoinsieme del proprio sovrainsieme di categoria direttamente sottostante.