L'esigenza di caratterizzare proprietà di sequenze di simboli è un problema comune ad un'ampia varietà di settori, dalla linguistica alla biologia computazionale, passando per molteplici campi dell'informatica, dall'interpretazione del software da parte del calcolatore alla verifica di correttezza dei sistemi di calcolo e reti di computer. Una tale variet`a nasce dall'interpretazione che si può dare dei simboli, che possono rappresentare termini di un linguaggio naturale, molecole, istruzioni di un linguaggio di programmazione, segnali digitali, messaggi di un protocollo di comunicazione o altri eventi.Lo studio rigoroso di questo problema generale può essere affrontato da due punti di vista che vedremo essere ortogonali. Da una parte, possiamo caratterizzare le sequenze di simboli come espressioni di un linguaggio generate attraverso le regole di una grammatica formale. Dall'altra, possiamo immaginare di definire una macchina astratta, comunemente detta automa, che ha l'obiettivo di riconoscere il linguaggio descritto da tali sequenze. Per via della vastità di questi argomenti, scopo del presente lavoro è introdurre il secondo di questi approcci formali, senza perdere di vista il legame forte che esiste con il primo.
Temi
Teoria degli automi per i linguaggi formali
di Alessandro Aldini
06.01.2014
Lo studio dei meccanismi del cervello umano deputati alla comprensione del linguaggio naturale, l'analisi del sequenziamento del genoma umano, la necessità per un calcolatore di interpretare un insieme di comandi. Sono situazioni apparentemente lontane tra loro, ma accomunate da uno stesso problema, ovvero l'esigenza di descrivere proprietà di sequenze di simboli, che possono rappresentare vocaboli, molecole, istruzioni di un linguaggio di programmazione e altro ancora. In questo ambito, il Novecento è stato teatro di studi complementari che hanno dato origine alla teoria dei linguaggi formali, come nel caso delle grammatiche di Chomsky, e degli automi riconoscitori, come nel caso delle macchine astratte di Kleene e di Turing. L'obiettivo di questo lavoro è introdurre in chiave storica, critica e scientifica gli elementi fondazionali della teoria degli automi riconoscitori di linguaggi formali.
Continua la lettura (non è necessario il reader PDF)
Scarica il file Pdf
