Linguaggio formale

Note

Un linguaggio è uno strumento per esprimere modelli. Ogni linguaggio è definito su un alfabeto, che è un insieme finito di simboli.

Esempi di linguaggio

Lingue naturali: Italiano, Francese, Inglese, Giapponese Linguaggi sintetici: C, Java, XML, JSON Linguaggi grafici: cartelli stradali, simboli di lavaggio negli indumenti Linguaggi acustici: musica, fischi degli arbitri sportivi

Esempi di alfabeto

Alfabeto latino: Binario:

Un linguaggio può essere usato per definire l’insieme di soluzioni di un problema, e per esprimere un problema stesso.

Stringhe

Note

Definiamo una stringa come una sequenza ordinata e finita di elementi di un alfabeto . Riguardante ad una stringa definiamo:

• Lunghezza di una stringa, cioè il numero di elementi come:
• Stringa di lunghezza nulla , con
• Insieme di tutte le stringhe (inclusivo di ) su :
• Operatore di concatenazione (omissibile)

Siccome l’operatore di concatenazione è binario, associativo e non commutativo, si può costruire il monoide libero dell’alfabeto , con elemento neutro .

Linguaggio su un alfabeto

Note

Un linguaggio su un alfabeto è un sottoinsieme di , e quindi un insieme di parole di .

Esempio

L’italiano è un linguaggio su . I file PDF sono un linguaggio su . I numeri in base sono un linguaggio su . Il DNA è un linguaggio codificabile su .

Notiamo che se , non necessariamente .

Siccome i linguaggi sono insiemi valgono le operazioni insiemistiche come . In particolare il complemento è definito rispetto ad , cioè: .

Concatenazioni tra linguaggi

Note

Dati un linguaggio su , e un linguaggio su , si ha che definito su è:

Si ha inoltre che dato un linguaggio e , è definita come la concatenazione di se stesso volte:

Definiamo inoltre l’operatore di un alfabeto, che indica stringhe fatte concatenando uno o più elementi dell’insieme. Per estensione ai linguaggi definiamo:

Nella pratica, l’intersezione tra linguaggi indica la compatibilità tra di loro, mentre la concatenazione di linguaggi consente di descrivere più agevolmente formati complessi.

Esempio di concatenazione

In questo esempio perché la concatenazione non è commutativa.

Esempio di concatenazione

Sia un alfabeto , allora . Per quanto riguarda ai linguaggi:

• Formato di pacchetto di dati su una rete
• Archivio di dati tar o zip:

Traduzioni

Note

Una traduzione è una mappa , cioè mette in corrispondenza parole di due linguaggi.

Famiglia di linguaggi

Note

Una famiglia di linguaggi è un insieme i cui elementi sono linguaggi. È chiusa rispetto ad un’operazione se .