โ† Theory of Computation learning path
Theory of Computation ยท Module 2 of 10

Deterministic finite automata

DFA: machines with finite memory.

๐Ÿ“– Key ideas

  1. A DFA has a finite set of states, an alphabet, a transition function, a start state and accepting states.
  2. For each state and symbol there is exactly one next state.
  3. A string is accepted if reading it ends in an accepting state.
  4. DFAs recognise exactly the regular languages.
  5. Example: a DFA for binary strings with an even number of 1s needs 2 states.
๐Ÿ’ก Real-life example: A DFA is like a turnstile: its state (locked or unlocked) changes with each coin or push, and it remembers nothing else.
DFADeterministic finite automaton
Transition functionRule giving next state from state and symbol
Accepting stateState where accepted strings end
Regular languageLanguage recognised by a finite automaton