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.

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.

In maniera formale, un linguaggio L è definito come ${\displaystyle L\subseteq \Sigma ^{*}}$, dove ${\displaystyle \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 ${\displaystyle \Sigma }$. Un linguaggio può essere di cardinalità finita, infinita o nulla. È importante notare che il linguaggio vuoto (denotato da ${\displaystyle L=\emptyset }$) differisce dal linguaggio composto esclusivamente dalla stringa muta (o parola vuota), denotata con e, ${\displaystyle \varepsilon }$ o ${\displaystyle \lambda }$.

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

• Il linguaggio vuoto
• ${\displaystyle L=\left\{\varepsilon \right\}}$ (linguaggio costituito solamente dalla stringa vuota)
• ${\displaystyle L^{\prime }=\left\{ababba,aaabbbaaa,aaabbbabaababb\right\}}$ (linguaggio finito)
• ${\displaystyle L^{\prime \prime }=a^{*}b^{*}}$ (linguaggio infinito definito da un'espressione regolare)
• ${\displaystyle 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).

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)

Sebbene siano stati definiti sopra alcuni esempi di linguaggi formali, è possibile esprimere alcuni linguaggi formali su ${\displaystyle \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 ${\displaystyle \Sigma }$ o l'insieme vuoto;
• L'insieme delle stringhe della forma ${\displaystyle 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

È possibile definire alcune operazioni unarie o binarie per generare un nuovo linguaggio a partire da linguaggi dati. Siano ${\displaystyle L_{1}}$ ed ${\displaystyle L_{2}}$ due linguaggi su un dato alfabeto.

• ${\displaystyle L=L_{1}\cdot L_{2}}$ è la concatenazione o giustapposizione dei due linguaggi. Consiste nell'insieme di tutte le stringhe vw tali che ${\displaystyle v\in L_{1}}$ e ${\displaystyle w\in L_{2}}$.
• ${\displaystyle L=L_{1}\cap L_{2}}$ è l'intersezione di ${\displaystyle L_{1}}$ ed ${\displaystyle L_{2}}$. Consiste nell'insieme di tutte le stringhe ${\displaystyle w/w\in L_{1}\land w\in L_{2}}$, ovvero tutte le stringhe contenute sia in ${\displaystyle L_{1}}$ che in ${\displaystyle L_{2}}$.
• ${\displaystyle L=L_{1}\cup L_{2}}$ è l'unione di ${\displaystyle L_{1}}$ ed ${\displaystyle L_{2}}$. Consiste nell'insieme di tutte le stringhe ${\displaystyle w/w\in L_{1}\lor w\in L_{2}}$, ovvero tutte le stringhe che appartengono ad almeno uno dei due linguaggi.
• ${\displaystyle L={\bar {L}}_{1}}$ è il complemento del linguaggio ${\displaystyle L_{1}}$. Consiste in tutte le stringhe ${\displaystyle w\in \Sigma ^{*}\setminus L_{1}}$, ovvero tutte stringhe sull'alfabeto ${\displaystyle \Sigma }$ che non sono contenute in ${\displaystyle L_{1}}$.
• ${\displaystyle L=L_{1}/L_{2}}$ è il quoziente destro di ${\displaystyle L_{1}}$ da ${\displaystyle L_{2}}$. Consiste in tutte le stringhe v per le quali esiste una stringa w in ${\displaystyle L_{2}}$ tale che ${\displaystyle vw\in L_{1}}$.
• ${\displaystyle L=L_{1}^{*}}$ è la star di Kleene. Consiste nel linguaggio ${\displaystyle \bigcup _{n\in \mathbb {N} }L_{1}^{n}}$, ovvero tutte le stringhe della forma ${\displaystyle w_{1}w_{2}\cdots w_{n}}$ tali che ${\displaystyle w_{i}/w_{i}\in L_{1}\land 0\leq i\leq n}$. Poiché ${\displaystyle L_{1}^{0}={\varepsilon }}$ si ha che la stringa muta ${\displaystyle \varepsilon \in L}$.
• ${\displaystyle L=L_{1}^{R}}$ è il riflesso. Se ${\displaystyle w=a_{1}a_{2}\cdots a_{n}}$ e ${\displaystyle w^{R}=a_{n}a_{n-1}\cdots a_{1}}$, il linguaggio L contiene tutte le stringhe ${\displaystyle w_{R}/w\in L_{1}}$, ovvero tutte le stringhe riflesse di ${\displaystyle L_{1}}$.
• Il mescolamento o shuffle di ${\displaystyle L_{1}}$ ed ${\displaystyle L_{2}}$ consiste di tutte le stringhe che si possono scrivere nella forma ${\displaystyle v_{1}w_{1}v_{2}w_{2}\cdots v_{n}w_{n}}$ tali che ${\displaystyle 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 ${\displaystyle w\in L}$ è un problema che coinvolge sia la teoria della calcolabilità che la teoria della complessità.

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

• Monoide
• Grammatica formale
• Stringa (linguaggi formali)
• Alfabeto (teoria dei linguaggi formali)
• Alfabeto concorrente
• Metalinguaggio

• Wikibooks contiene testi o manuali sul linguaggio formale
• Wikiversità contiene risorse sul linguaggio formale
• Wikimedia Commons contiene immagini o altri file sul linguaggio formale

• (EN) formal language, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Linguaggio formale, su MathWorld, Wolfram Research.

Portale Informatica

Portale Linguistica

Portale Matematica