Finite State Automata
- Has a finite number of states
- Machine initialized in certain state, "consumes" a sequence of characters one-by-one.
- State updated after consuming each symbol based on current state and consumed symbol.
- Once whole input string is consumed, machine terminates and accepts / rejects string based on final state.