Apri il menu principale

Linguaggio formale

insieme di stringhe di lunghezza finita costruite sopra un alfabeto finito, che possono essere soggette a regole specifiche
(Reindirizzamento da Linguaggi formali)

Per linguaggio formale, in matematica, logica, informatica e linguistica, 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.

StoriaModifica

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.

DescrizioneModifica

CaratteristicheModifica

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 formaleModifica

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

Esempi di linguaggi formaliModifica

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 formaliModifica

È 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 un stringa w ed un linguaggio L, verificare se   è un problema che coinvolge sia la teoria della calcolabilità che la teoria della complessità.

BibliografiaModifica

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

Altri progettiModifica

Collegamenti esterniModifica

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àLCCN (ENsh85050802 · GND (DE4017848-1 · NDL (ENJA00576869