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 ${\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).

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 ${\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

Operazioni sui linguaggi formali

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

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.

Teoria degli automi: linguaggi formali e grammatiche formali
Gerarchia di Chomsky	Grammatica formale	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 proprio della categoria immediatamente sovrastante.

Controllo di autorità	Thesaurus BNCF 5999 · LCCN (EN) sh85050802 · GND (DE) 4017848-1 · BNF (FR) cb11967270h (data) · J9U (EN, HE) 987007545721205171 · NDL (EN, JA) 00576869

Portale Informatica

Portale Linguistica

Portale Matematica