🎰 Automata (acceptor) §

= a 🦾 State machine representing an indicator function ($X\to \{0,1\}$) over all possible words

Families §

Name	Storage	Rule Type	Complexity
🏁 Finite state automata	none	$A->xB,A->x$	n (linear)
📚 Pushdown automata	stack	$\beta A\gamma ->\beta \delta \gamma$	$n^3$ (cubic)
🎞 Linear-bounded automata	finite tape length	$A->\beta$	$e^n$ (exponential)
👑 Turing Machine	infinite	$\alpha ->\beta$	undecideable

📖 Example: §

1️⃣ Deterministic finite automaton that checks the validity of e.g. b → false or 00 → true

graph LR
q0 --"0"--> q1
q0 --"1"--> q2
q1 --"0"--> q3
q3 --> qf
q1 --"1"--> q3