In this five-section chapter, we cover finite automata that represents perhaps the simplest language-accepting rewriting systems. In Section 5.1, we define their basic versions. Then, in Section 5.2, we introduce finite automata that read a symbol during every single computational step. In Section 5.3, we study deterministic finite automata. In Section 5.4, we cover several reduced and minimal versions of finite automata. Finally, in Section 5.5, we define regular expressions and demonstrate the equivalence between them and finite automata.

Chapter Contents:

• 5.1 Mathematical elements of finite automata
• 5.1.1 How to specify finite automata
• 5.1.1.1 Informal description
• 5.1.1.2 State table
• 5.1.1.3 State diagram
• 5.1.1.4 Formal description
• 5.2 Finite automata that always read
• 5.3 Determinism
• 5.4 Reduction and minimization
• 5.5 Regular expressions

Inspec keywords: finite automata; deterministic automata; rewriting systems; formal languages

Other keywords: simplest language-accepting rewriting systems; regular expressions; deterministic finite automata

Subjects: Automata theory; Formal languages and computational linguistics