🏁 Finite state automata (FSA)

=== 🎰 Automata without storage==

Formal definition

• Σ = a finite, nonempty input alphabet
• Q = a finite set of states
• δ = a series of transition functions
• q0 = the starting state
• F = the set of accepting (final) states

Types

• 1️⃣ Deterministic finite automata
• 🔢 Non-deterministic finite automata

Properties

• Equivalent to 🔡 Regular Expressions
• Linear time complexity

Applications

• → 🌳 Parsing

Related

• FSA with an output: 🛠 Finite state transducer