lezione
lezione
Linguaggio
Tipo di risorsa Tipo: lezione
Materia di appartenenza Materia: Linguaggi formali e automi

Introduzione modifica

La teoria dei linguaggi formali nasce con l'obiettivo di studiare in modo sistematico le regolarità che si manifestano nei linguaggi naturali.

Con il passare del tempo la disciplina si è sviluppata fino a comprendere diversi strumenti concettuali di grande interesse per l'informatica teorica, molti dei quali verranno presentati in questo corso.

Per comprenderli appieno è necessario comprendere che cosa si intenda, in questo contesto, con la parola linguaggio; lo scopo del presente modulo è proprio la presentazione di tale concetto, unitamente alla definizione delle principali idee ad esso collegate.

L'alfabeto modifica

Alla base di ogni linguaggio formale c'è un alfabeto, inteso semplicemente come un insieme finito di simboli. Anche se la parola richiama subito alla memoria le lettere con cui componiamo le parole, in questo contesto il termine va interpretato in un senso più generale, ossia come un insieme finito di simboli di qualunque genere, siano essi lettere, cifre o qualunque tipologia di segno.

Nella teoria dei linguaggi formali l'alfabeto ha un ruolo centrale, in quanto ogni parola presente nel linguaggio è derivata da esso. Proprio per questo motivo quando si studia o si progetta un linguaggio è fondamentale prestare grande attenzione all'alfabeto, poiché la sua comprensione è il primo passo verso la costruzione di messaggi sensati.

Stabilita l'esistenza di un alfabeto, il suo impiego principale consiste nella produzione delle parole, oggetto di studio della prossima sezione.

La parola modifica

Dato un alfabeto  , una parola è una successione finita di simboli presi dall'alfabeto. Indicando con   tali simboli, la parola   si scriverà semplicemente giustapponendo i simboli stessi:  .

Data una parola  , con la notazione   si intende la lunghezza della parola, da interpretare come il numero di simboli di cui è composta. Ad esempio, la parola   formata utilizzando le lettere dell'alfabeto latino è composta da quattro simboli, quindi  .

In qualche caso può essere utile considerare la parola vuota o stringa vuota, indicata convenzionalmente con la lettera   oppure con  . In questo caso,  .

Le potenze di un alfabeto modifica

Un alfabeto   può essere interpretato in due modi diversi: o come insieme di simboli con cui costruire le parole, oppure come insieme di parole composte da un simbolo solo. Considerando che le due interpretazioni hanno significati profondamente diversi è stato deciso di distinguerle indicando con   l'insieme che contiene parole.

Intuitivamente si potrà supporre l'esistenza di un insieme   che contiene tutte le parole generate dall'alfabeto   e composte da due simboli; più in generale,   indicherà l'insieme di tutte le parole generate dall'alfabeto   e composte da n simboli.

Gli insiemi   prendono il nome di potenze dell'alfabeto  .

Particolare attenzione merita la potenza  , contenente tutte le stringhe generate dall'alfabeto e dotate di lunghezza nulla: evidentemente questa potenza contiene solamente la stringa nulla. Potremo quindi scrivere  .

Gli operatori di Kleene modifica

L'insieme alfabeto contiene tutto il potenziale necessario per creare un linguaggio, in quanto da esso possono essere create tutte le possibili parole. Un modo per generarle potrebbe consistere nella creazione di un insieme all'interno del quale mettere prima tutte le parole di lunghezza 1, poi tutte le parole di lunghezza 2, e così via; questo obiettivo è raggiungibile impiegando l'unione insiemistica e sfruttando le potenze dell'alfabeto.

Formalmente diremo che, dato un alfabeto  , l'insieme di tutte le parole generabili dall'alfabeto si indica con la notazione   ed è tale che:

 

L'operatore star modifica

L'operatore indicato con   è chiamato star di Kleene ed è impiegato per generare un monoide libero sull'insieme cui viene applicato.

L'operatore cross modifica

La concatenazione di parole modifica

La concatenazione di due stringhe   e   è la stringa   ottenuta giustapponendo tutti i simboli della stringa   a quelli della stringa  . Più precisamente, indicando con   la stringa   e con   la stringa  , la stringa  , concatenazione delle parole v e w, si scriverà:  , inoltre il generico simbolo   assumerà il valore   quando   e   quando  . Si può inoltre concludere che  ,   e  .