Teoria degli automi per linguaggi formali

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.