🏁 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