Linguaggio formale

Da Wikipedia, l'enciclopedia libera.
(Reindirizzamento da Linguaggio formale (matematica))

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.

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

Bibliografia[modifica | modifica wikitesto]

  • (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[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à GND: (DE4017848-1