Finite automaton

A finite automaton is a machine with finitely many states that reads an input string and accepts or rejects it according to its transitions and accepting states.

Deterministic finite automaton: A finite automaton with exactly one transition for each state and input symbol. Its single possible computation makes acceptance direct to test.
Alphabet (formal languages): A finite set of symbols from which strings in a formal language are formed. Automaton transitions are defined for symbols from this set.
Lexical analysis: The compiler phase that groups source-code characters into tokens. Token patterns are commonly recognized using finite automata.
Pushdown automaton: A finite-state machine augmented with a stack, enabling recognition of some nonregular languages. Its unbounded stack can track nested structure beyond finite automata's memory.
Warren McCulloch: An American neurophysiologist who helped develop early mathematical models of neural activity. His collaboration with Walter Pitts supplied an influential precursor to finite-state computation.
Nondeterministic finite automaton: A finite automaton that may have several possible transitions for an input symbol. Acceptance holds when at least one possible computation reaches an accepting state.
String (computer science): A finite sequence of symbols drawn from an alphabet. An automaton processes its input one symbol at a time.
Regular expression: A notation for describing regular languages using operations such as union, concatenation, and repetition. Regular expressions can be compiled into finite automata for matching.
Turing machine: A computational model with an unbounded tape and rules for reading, writing, and moving along it. Its unbounded memory allows computations finite automata cannot perform.
Walter Pitts: An American logician whose work with Warren McCulloch modeled neural activity mathematically. Their 1943 neural model helped establish a mathematical view of state-based computation.

Linked from 11 pages