Linguaggio formale (matematica)

In matematica, logica, informatica e linguistica, per linguaggio formale si intende un insieme di stringhe di lunghezza finita costruite sopra un alfabeto finito, cioè sopra un insieme finito di oggetti tendenzialmente semplici che vengono chiamati caratteri, simboli o lettere.

Di un linguaggio formale può far parte o meno la stringa muta o parola vuota, cioè la sequenza costituita da zero caratteri: questa spesso viene denotata come e, ε o λ: qui preferiamo usare μ.

Un linguaggio può essere finito o infinito in quanto non si pongono limiti alla lunghezza delle stringhe.

Un tipico alfabeto potrebbe essere A := {a, b} e tipiche stringhe su questo alfabeto

ababba aaabbbaaa aaabbbabaababb .

Esempi di linguaggi formali su A sono:

il linguaggio di tutte le stringhe che contengono lo stesso numero di a e di b;
lo stesso insieme di tutte le parole su A e lo stesso insieme vuoto;
l'insieme delle stringhe della forma aⁿ con n numero primo;
l'insieme dei programmi in un dato linguaggio di programmazione che si dimostrano sintatticamente corretti;
l'insieme delle stringhe che, immesse in una macchina di Turing, la fanno evolvere fino ad un arresto.

Un linguaggio formale può essere definito in una grande varietà di modi.

come insieme delle stringhe derivate nell'ambito di una grammatica formale (v. gerarchia di Chomsky);
stringhe fornite da una espressione razionale;
stringhe accettate da qualche automa, come una macchina di Turing o un riconoscitore a stati finiti;
nell'ambito di un insieme di domande la cui risposta può essere solo SI o NO, le domande a risposta affermativa (v. problema di decisione).

I linguaggi si possono comporre con molte operazioni e in tal modo si possono ottenere molti linguaggi a partire da un insieme di linguaggi dati. Con L₁ ed L₂ denotiamo due linguaggi sopra un dato alfabeto.

La concatenazione o giustapposizione L₁L₂ consiste di tutte le stringhe della forma vw dove v è una stringa di L₁ e w una stringa di L''₂.
L' intersezione di L₁ ed L₂ consiste di tutte le stringhe contenute sia in L₁ che in L₂.
L' unione di L₁ ed L₂ consiste di tutte le stringhe che sono contenute in L₁ o in L₂.
Il complemento del linguaggio L₁ consiste di tutte le stringhe sopra l'alfabeto che non sono contenute in L₁.
Il quoziente destro L₁/L₂ di L₁ da L₂ consiste di tutte le stringhe v per le quali esiste una stringa w in L₂ tale che vw si trova in L₁.
La star di Kleene L₁* consiste di tutte le stringhe che possono essere scritte nella forma w₁w₂...w_n con le stringhe w_i in L₁ ed n ≥ 0. Si noti che questo include la stringa muta in quanto si ammette n = 0.
Il riflesso L₁^R contiene le stringhe riflesse, capovolte, di tutte le stringhe in L₁.
Il mescolamento o shuffle di L₁ ed L₂ consiste di tutte le stringhe che si possono scrivere nella forma v₁w₁v₂w₂...vnwn, dove n ≥ 1 and v₁,...,vn sono stringhe tali che la concatenazione v₁...vn si trova in L₁ e w₁,...,wn sono stringhe tali che w₁...wn si trova L''₂.

Una tipica questione che si pone sopra un linguaggio formale riguarda quanto sia oneroso decidere se una data parola appartiene o meno al linguaggio. Essa ricade sotto il dominio della teoria della computabilità e della teoria della complessità.

Linguaggi formali

Gourt Home::Gourt :: Linguaggio formale (matematica)