Finite Automata as Regular Language Recognizers
| Autor: | Luca Breveglieri, Angelo Morzenti, Stefano Crespi Reghizzi |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Discrete mathematics
TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES Nested word Theoretical computer science Computer science ω-automaton Nonlinear Sciences::Cellular Automata and Lattice Gases TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Deterministic finite automaton DFA minimization Deterministic automaton Quantum finite automata Automata theory Nondeterministic finite automaton Computer Science::Formal Languages and Automata Theory |
| Zdroj: | Texts in Computer Science ISBN: 9783030048785 Texts in Computer Science ISBN: 9781447155133 |
| Popis: | In this chapter we introduce finite automata, discuss their properties, and present their role as recognizers of regular languages, in particular at the lexical level of compilation. After an overview of general string recognition algorithms and automata, we focus on finite-state devices. We define the notions of state accessibility, determinism, spontaneous move, ambiguity, and we analyze the relations between finite automata and grammars. We present the basic constructions for cleaning, determinizing, and minimizing automata. Then we spend more time on the methods for deriving regular expressions from automata, and, conversely, for obtaining finite deterministic recognizers from regular expressions; the latter methods are also used for eliminating nondeterminism. Finally, by exploiting their relation to finite automata, we introduce regular expressions extended with the operations of complement and intersection. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|