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 Σ^{*}$ , dove $Σ^{*}$ (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 $Σ$ . 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, $ε$ o $λ$ .

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

Il linguaggio vuoto
$L = {ε}$ (linguaggio costituito solamente dalla stringa vuota)
$L^{'} = {a b a b b a, a a a b b b a a a, a a a b b b a b a a b a b b}$ (linguaggio finito)
$L^{''} = a^{*} b^{*}$ (linguaggio infinito definito da un'espressione regolare)
$L^{'''} = Σ^{*}$

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 $Σ$ 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^{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}$ è lTemplate:'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}$ è lTemplate:'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 Σ^{*} ∖ L_{1}$ , ovvero tutte stringhe sull'alfabeto $Σ$ 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 $v w \in L_{1}$ .
$L = L_{1}^{*}$ è la star di Kleene. Consiste nel linguaggio $⋃_{n \in ℕ} L_{1}^{n}$ , ovvero tutte le stringhe della forma $w_{1} w_{2} \dots w_{n}$ tali che $w_{i} / w_{i} \in L_{1} \land 0 \leq i \leq n$ . Poiché $L_{1}^{0} = ε$ si ha che la stringa muta $ε \in L$ .
$L = L_{1}^{R}$ è il riflesso. Se $w = a_{1} a_{2} \dots a_{n}$ e $w^{R} = a_{n} a_{n - 1} \dots 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} \dots v_{n} w_{n}$ tali che $n \geq 1 \land {v_{1} \dots v_{n}} \in L_{1} \land {w_{1} \dots w_{n}} \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

Voci correlate

Altri progetti

Template:Interprogetto

Collegamenti esterni

Template:Collegamenti esterni

Template:Linguaggi formali e grammatiche

Template:Controllo di autorità Template:Portale

Linguaggio formale

Indice

Storia

Descrizione

Caratteristiche

Definizione di linguaggio formale

Esempi di linguaggi formali

Operazioni sui linguaggi formali

Bibliografia

Voci correlate

Altri progetti

Collegamenti esterni

Menu di navigazione

Linguaggio formale

Storia

Descrizione

Caratteristiche

Definizione di linguaggio formale

Esempi di linguaggi formali

Operazioni sui linguaggi formali

Bibliografia

Voci correlate

Altri progetti

Collegamenti esterni

Menu di navigazione

Ricerca