# Linguaggio formale

Per linguaggio formale, in matematica, logica, informatica e linguistica, si intende un insieme di stringhe costruite sopra un alfabeto, cioè sopra un insieme di oggetti tendenzialmente semplici che vengono chiamati caratteri, simboli o lettere. Sovente si suppone che l'alfabeto sul quale è costruito il linguaggio sia un insieme finito.

## Storia

Il primo linguaggio formale di cui si ha notizia è introdotto da Gottlob Frege nel suo Begriffsschrift (1879), tradotto in italiano come "Ideografia" e che il sottotitolo definisce "un linguaggio in formule del pensiero puro, a imitazione di quello aritmetico".
La teoria dei linguaggi formali nasce negli anni '50 nell'ambito della linguistica, come modo di comprendere le regolarità dei linguaggi naturali.

## Descrizione
### Caratteristiche

In maniera formale, un linguaggio L è definito come $L\subseteq \Sigma ^{*}$, dove $\Sigma ^{*}$ (in cui l'asterisco indica la star di Kleene) rappresenta l'insieme di tutte le sequenze finite (stringhe o parole) che è possibile formare con l'alfabeto $\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, $\varepsilon$ o $\lambda$.
Ad esempio, dato l'alfabeto $\Sigma =\left\{a,b\right\}$ alcuni possibili linguaggi su tale alfabeto sono:
* Il linguaggio vuoto
* $L=\left\{\varepsilon \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 linguaggio formale

Un linguaggio formale può essere definito in una grande varietà di modi equivalenti fra loro:
* L'insieme delle stringhe derivate da una grammatica generativa
* L'insieme delle stringhe fornite da un'espressione regolare
* L'insieme delle stringhe accettate 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 $\Sigma$ 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 $\Sigma$ o l'insieme vuoto;
* L'insieme delle stringhe della forma $a^{n}$ 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 linguaggi dati. Siano $L_{1}$ ed $L_{2}$ due linguaggi su un dato alfabeto.
* $L=L_{1}\cdot 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_{1}$ ed $L_{2}$. Consiste nell'insieme di tutte le stringhe $w/w\in L_{1}\land w\in L_{2}$, ovvero tutte le stringhe contenute sia in $L_{1}$ che in $L_{2}$.
* $L=L_{1}\cup L_{2}$ è l'unione di $L_{1}$ ed $L_{2}$. Consiste nell'insieme di tutte le stringhe $w/w\in L_{1}\lor 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_{1}$. Consiste in tutte le stringhe $w\in \Sigma ^{*}\setminus L_{1}$, ovvero tutte stringhe sull'alfabeto $\Sigma$ che non sono contenute in $L_{1}$.
* $L=L_{1}/L_{2}$ è il quoziente destro di $L_{1}$ da $L_{2}$. Consiste in tutte le stringhe v per le quali esiste una stringa w in $L_{2}$ tale che $vw\in L_{1}$.
* $L=L_{1}^{*}$ è la star di Kleene. Consiste nel linguaggio $\bigcup _{n\in \mathbb {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}\land 0\leq i\leq n$. Poiché $L_{1}^{0}={\varepsilon }$ si ha che la stringa muta $\varepsilon \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_{1}$.
* Il mescolamento o shuffle di $L_{1}$ ed $L_{2}$ 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\geq 1\land \left\{v_{1}\cdots v_{n}\right\}\in L_{1}\land \left\{w_{1}\cdots w_{n}\right\}\in L_{2}$.
Uno dei problemi più comuni legati ai linguaggi formali riguarda il membership problem. Data una 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à.