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.

Caratteristiche

[modifica | modifica wikitesto]

In maniera formale, un linguaggio L è definito come , 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 ) differisce dal linguaggio composto esclusivamente dalla stringa muta (o parola vuota), denotata con e, o .

Ad esempio, dato l'alfabeto alcuni possibili linguaggi su tale alfabeto sono:

  • Il linguaggio vuoto
  • (linguaggio costituito solamente dalla stringa vuota)
  • (linguaggio finito)
  • (linguaggio infinito definito da un'espressione regolare)

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

[modifica | modifica wikitesto]

Un linguaggio formale può essere definito in una grande varietà di modi equivalenti fra loro:

Esempi di linguaggi formali

[modifica | modifica wikitesto]

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

[modifica | modifica wikitesto]

È possibile definire alcune operazioni unarie o binarie per generare un nuovo linguaggio a partire da linguaggi dati. Siano ed due linguaggi su un dato alfabeto.

  • è la concatenazione o giustapposizione dei due linguaggi. Consiste nell'insieme di tutte le stringhe vw tali che e .
  • è l'intersezione di ed . Consiste nell'insieme di tutte le stringhe , ovvero tutte le stringhe contenute sia in che in .
  • è l'unione di ed . Consiste nell'insieme di tutte le stringhe , ovvero tutte le stringhe che appartengono ad almeno uno dei due linguaggi.
  • è il complemento del linguaggio . Consiste in tutte le stringhe , ovvero tutte stringhe sull'alfabeto che non sono contenute in .
  • è il quoziente destro di da . Consiste in tutte le stringhe v per le quali esiste una stringa w in tale che .
  • è la star di Kleene. Consiste nel linguaggio , ovvero tutte le stringhe della forma tali che . Poiché si ha che la stringa muta .
  • è il riflesso. Se e , il linguaggio L contiene tutte le stringhe , ovvero tutte le stringhe riflesse di .
  • Il mescolamento o shuffle di ed consiste di tutte le stringhe che si possono scrivere nella forma tali che .

Uno dei problemi più comuni legati ai linguaggi formali riguarda il membership problem. Data una stringa w ed un linguaggio L, verificare se è un problema che coinvolge sia la teoria della calcolabilità che la teoria della complessità.

Voci correlate

[modifica | modifica wikitesto]

Altri progetti

[modifica | modifica wikitesto]

Collegamenti esterni

[modifica | modifica wikitesto]
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 (ENsh85050802 · GND (DE4017848-1 · BNF (FRcb11967270h (data) · J9U (ENHE987007545721205171 · NDL (ENJA00576869