REGULAR LANGUAGES: TO FINITE AUTOMATA AND BEYOND - SUCCINCT DESCRIPTIONS AND OPTIMAL SIMULATIONS
Pighizzini, G., Boldi, P., Prigioniero, L. · Archivio Istituzionale della Ricerca (Universita Degli Studi Di Milano) · 2020
It is well known that regular -or type 3 -languages are equivalent to finite automata.Nevertheless, many other characterizations of this class of languages in terms of computational devices and generative models are present in the literature.For example, by suitably restricting more general models such as context-free grammars, pushdown automata, and Turing machines, that characterize wider classes of languages, it is possible to obtain formal models that generate or recognize regular languages only.The resulting formalisms provide alternative representations of type 3 languages that may be significantly more concise than other models that share the same expressing power.The goal of this work is to investigate these formal systems from a descriptional complexity perspective, or, in other words, to study the relationships between their sizes, namely the number of symbols used to write down their descriptions.We also present some results related to the investigation of the famous question posed by Sakoda and Sipser in 1978, concerning the size blowups from nondeterministic finite automata to twoway deterministic finite automata.