Abstract
The study of the mechanisms of the human brain that are dedicated to the comprehension of the natural language, as well as the human genome sequence analysis, as well as the computer capability of interpreting a set of commands, represent all apparently different situations. Actually, they share the same underlying problem, that is the need for describing properties of sequences of symbols, which can represent terms, molecules, instructions of a programming language and so on.
In this setting, in the 20th century several orthogonal studies created the base behind the foundations of formal languages, as in the case of Chomsky’s grammars, and of automata theory, as in the case of the abstract machines by Kleene and Turing.
The objective of this paper is to propose an historical, critical, and scientific survey about the constituting elements of automata theory applied to formal languages.
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.
Citazione
Alessandro Aldini “Teoria degli automi per i linguaggi formali”, in “APhEx 9”, 2014, pp. 36.
Numero della rivista
Visualizza e scarica il file PDF
Vai agli indici
AUTORI&AUTRICI
Ricercatore di Informatica presso l'Università di Urbino "Carlo Bo", Dipartimento di Scienze di Base e Fondamenti. Le sue aree di ricerca riguardano metodi formali per la verifica di sistemi software e hardware. É co-direttore della International SummerSchool on Foundations of Security Analysis and Design. Ulteriori informazioni sono reperibili sulla sua pagina web personale: http://www.sti.uniurb.it/aldini/