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à.

Bibliografia

• (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.

Voci correlate

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

Altri progetti

Altri progetti

• Wikibooks
• Wikiversità
• Wikimedia Commons

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

Collegamenti esterni

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