Jargon Automata in Finite State Automata
By Xah Lee. Date: . Last updated: .
- ok, a bit xah edu corner extempore❗ (from twitter)
- yesterday, i took a hour to think about the terminology “automata”, as in NFA and DFA.
- NFA = Non-deterministic Finite Automata, DFA = deterministic Finite Automata.
- the word “automaton” means “machine”. It came from greek, meaning “act by itself”. Basically, we'd call a robot.
- NFA and DFA are models of computation. They are needed to implement regex.
- now, the word “automata” is not a good terminology. like, what the heck you mean “automata”? or “robot”? likewise Turing Machine.
- by no means NFA or DFA act by themselfs, contrary to the word's root. They are “auto” as much as a dynamical system of math is auto.
- recursive xah's edu corner: inner note: Automaton, is a gift Zeus gave to Europa. The story goes thus:
- Zeus, changed himself into a big white bull, then abducted Europa.
- Zeus gave Europa 3 gifts: Talos, Laelaps, and a javelin that never missed!
- Laelaps is a dog that never fails to catch the game!
- Talos, is a automaton! basically, a giant robot that protects her! isn't that amazing? we have robot few thousand years back.
- O, btw, Zeus also gave Europa a entire island, Crete. What a lucky girl. Mate the most powerful man, and with these godsend gifts.
- back to automata. Now, that term is bad. So what's better? 1st, we think about what Finite State Machines really means.
- “machine” doesn't seem a proper term neither. cuz it's not a mechanical device.
- what do u think of when you hear “machine”? gears and cogs, mechanics, right?
- as we know, they are models of computation. but “finite state model”, isn't ideal neither.
- cuz the word “model”, we think of swim suite model, toy model train.
- lets consult math jargons to see what's over there. they have, algebra, group theory, topology, non-euclidean geometry, vector space …
- in math land, the jargons are not consistent neither. some are “theory”, some are “algebra”, some are “*ology”, some are “space”.
- but they are all a “system”. A set of definitions. Most are inert eg: algebras and groups, but some not, implies action just as NFA.
- eg dynamical systems, orbits, mandebrot set, fractal, iterated function system (IFS), chaos theory
- so, in the end, i think a better term for “automata” of NFA/DFA, is “system”, as in formal language aka formal system.
- i.e. DFA should be called DFS for deterministic finite state system.
- that concludes today's xah edu corner. but lol, automata just sound cool, and i love the story of Europa.