Skip to content

AEiE0801 Finite automata

Finite-automata fundamentals

  • A finite automaton is an abstract machine with a finite number of states.
  • A finite state machine (FSM) changes state on input symbols according to a transition rule.
  • A language is regular if some finite automaton can recognize it.
  • A DFA has exactly one next state for each state-input pair.
  • An NFA may have zero, one, or many next states for a state-input pair.
  • An epsilon-NFA additionally allows transitions without consuming input.
  • A regular expression is an algebraic description of a regular language.

DFA, NFA, and FSM distinctions

Machine Transition rule Acceptance idea Expressive power
DFA One next state per symbol Single computation path Regular languages
NFA Set of possible next states Accept if any path accepts Same as DFA
epsilon-NFA NFA plus epsilon moves Accept if any path accepts Same as DFA
  • DFA and NFA are expressively equivalent.
  • Every DFA is already a restricted NFA, and every NFA can be converted to an equivalent DFA.
  • NFA is often easier to design; DFA is often easier to implement.
  • Converting NFA to DFA may increase the number of states exponentially.
  • State minimization is standard for DFA, not directly for NFA.

Output-model distinction often confused with automata

Model Output depends on Recognition cue
Mealy machine Present state and present input Output on transitions
Moore machine Present state only Output on states
  • Mealy and Moore machines are transducers, not language recognizers in the strict FA sense.
  • Mealy output can change immediately with input.
  • Moore output changes only when the state changes.

Formal model and regex operators

\[ M=(Q, \Sigma, \delta, q_0, F) \]
  • \(Q\): finite set of states.
  • \(\Sigma\): input alphabet.
  • \(\delta: Q \times \Sigma \to Q\) for DFA.
  • \(q_0\): start state.
  • \(F \subseteq Q\): accepting states.

For NFA,

\[ \delta: Q \times \Sigma \to 2^Q \]

and for epsilon-NFA,

\[ \delta: Q \times (\Sigma \cup \{\varepsilon\}) \to 2^Q. \]
Regex form Meaning
\(r+s\) Union
\(rs\) Concatenation
\(r^*\) Zero or more repetitions
\(\varepsilon\) Empty string
\(\emptyset\) Empty language
  • Precedence is usually star, concatenation, then union.
  • \((a+b)^*\) means any string over \(\{a,b\}\).
  • \(ab^*\) means one \(a\) followed by zero or more \(b\).
  • Regular languages are closed under union, concatenation, Kleene star, complement, intersection, difference, and reversal.

Minimization and recognition cues

  • Remove unreachable states first.
  • Equivalent states cannot be distinguished by any input string.
  • Final and non-final states can never be equivalent.
  • Partition refinement is the standard minimization method.
  • If every state-symbol pair must be filled exactly once, the diagram is DFA style.
  • If the stem asks for the smallest equivalent machine, think minimization after reachability check.
  • If a language only needs finite memory such as parity, modulo count, or fixed suffix detection, FA is appropriate.

Common traps in finite automata

  • NFA is not more powerful than DFA for regular languages.
  • Minimization does not change the language.
  • A missing transition in a DFA means the machine is incomplete unless a dead state is assumed.
  • Regular expressions describe languages, not parse trees.
  • A finite automaton cannot recognize nested parentheses of arbitrary depth.

One-step examples for finite automata

  • Strings over \(\{0,1\}\) with even number of ones need two states: even and odd.
  • The regex for all binary strings ending in 01 is \((0+1)^*01\).
  • Strings of length divisible by 3 can be recognized by a 3-state DFA.

Finite-automata revision box

DFA and NFA accept exactly the regular languages. NFA may branch, DFA may not. Mealy output is on transitions, Moore output is on states. Minimization simplifies DFA form but does not change expressive power.