Anzeige
Erschienen in:
2022 | OriginalPaper | Buchkapitel
Finite Automata and Regular Grammars
verfasst von : Alberto Pettorossi
Erschienen in: Automata Theory and Formal Languages
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this chapter we introduce the notions of the deterministic finite automata and the nondeterministic finite automata, and we show their equivalence (see Theorem 2.1.14 on page 29). We also prove the equivalence between deterministic finite automata and S-extended type 3 grammars. We introduce the notion of a regular expression (see Section 2.5 on page 41) and we prove the equivalence between regular expressions and deterministic finite automata. We also study the problem of minimizing the number of states of the finite automata and we present a parser for type 3 languages. Finally, we introduce some generalizations of the finite automata and we consider various closure and decidability properties for type 3 languages.