Linguaggio formale (matematica)

Da Wikipedia, l'enciclopedia libera.

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

In maniera formale, un linguaggio L è definito come L \subseteq \Sigma^{*}, dove \Sigma^{*} (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 \Sigma. 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, \varepsilon o \lambda.

Ad esempio, dato l'alfabeto \Sigma = \left \{ a, b \right \} alcuni possibili linguaggi su tale alfabeto sono:

  • il linguaggio vuoto
  • L = \left \{ \varepsilon \right \} (linguaggio costituito solamente dalla stringa vuota)
  • L^{\prime} = \left \{ ababba, aaabbbaaa, aaabbbabaababb \right \} (linguaggio finito)
  • L^{\prime\prime} = a^{*} b^{*} (linguaggio infinito definito da un'espressione regolare)
  • L^{\prime\prime\prime} = \Sigma^{*}

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

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

Esempi di linguaggi formali[modifica | modifica sorgente]

Sebbene siano stati definiti sopra alcuni esempi di linguaggi formali, è possibile esprimere alcuni linguaggi formali su \Sigma 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 \Sigma 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[modifica | modifica sorgente]

È possibile definire alcune operazioni unarie o binarie per generare un nuovo linguaggio a partire da lunguaggi 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 è l'intersezione di L_1 ed L_2. Consiste nell'insieme di tutte le stringhe  w / w \in L_1 \and w \in L_2, ovvero tutte le stringhe contenute sia in L_1 che in L_2.
  • L = L_1 \cup L_2 è l'unione di L_1 ed L_2. Consiste nell'insieme di tutte le stringhe  w / w \in L_1 \or 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 \Sigma^{*} \setminus L_1, ovvero tutte stringhe sull'alfabeto \Sigma che non sono contenute in L_1.
  • L = L_1 \backslash 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 vw \in L_1.
  • L = L_1^{*} è la star di Kleene. Consiste nel linguaggio \bigcup_{n \in \N} L_1^{n}, ovvero tutte le stringhe della forma w_1 w_2 \cdots w_n tali che w_i / w_i \in L_1 \and 0 \le i \le n. Poiché L_1^{0} = { \varepsilon } si ha che la stringa muta \varepsilon \in L.
  • L = L_1^{R} è il riflesso. Se w = a_1 a_2 \cdots a_n e w^{R} = a_n a_{n-1} \cdots 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 \cdots v_n w_n tali che n \ge 1 \and \left \{ v_1 \cdots v_n \right \} \in L_1 \and \left \{ w_1 \cdots w_n \right \} \in L_2.

Uno dei problemi più comuni legati ai linguaggi formali riguarda il membership problem. Data un 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[modifica | modifica sorgente]

  • (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-0321462251.

Voci correlate[modifica | modifica sorgente]

Collegamenti esterni[modifica | modifica sorgente]

Informatica Portale Informatica: accedi alle voci di Wikipedia che trattano di Informatica
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 sottostante.