๐ŸŽฐ Automata (acceptor)

= a ๐Ÿฆพ State machine representing an indicator function () over all possible words


NameStorageRule TypeComplexity
๐Ÿ Finite state automatanonen (linear)
๐Ÿ“š Pushdown automatastack (cubic)
๐ŸŽž Linear-bounded automatafinite tape length (exponential)
๐Ÿ‘‘ Turing Machineinfiniteundecideable

๐Ÿ“– 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