equivalence between finite automata and REs

Cards (12)

  • FROM REs TO FINITE AUTOMATA
    Theorem:
    • Every language defined by a regular expression R is also defined by a-NFA E.
    • Thompson method
  • BASIS STEP
  • INDUCTION STEP
  • EXAMPLE
  • EXAMPLE (cont.)
  • FROM FINITE AUTOMATA TO REs
    • Construction of paths (has many repetitions, is onerous, and may provide long/complex REs if we dont simplify them)
    • State elimination (will study only this one)
  • NORMALIZING e-NFAs
  • EXAMPLE
  • STATE ELIMINATION
    Given a noramlized e-NFA:
  • STATE ELIMINATION (cont.)
  • STATE ELIMINATION (cont.)
  • STATE ELIMINATION (cont.)