equivalence between dfas and ε-nfas

• FINITE AUTOMATA WITH ε-TRANSITIONS

  What is an ε-transition?

  A spontaneous transition (empty-string transition) that can be followed without receiving/consuming/processing input symbols (i.e., for any input symbol).

  An ε-NFA is an NFA with ε transitions.
• EXAMPLE

  ε-NFA that recognizes decimal numbers.

  • Signal + or - optional
  • Sequence of digits (0,...,9)
  • A decimal point (.)
  • Another sequence of digits
  • At least one of the sequences of digits is non-empty
  • ∑ = {+,-,.,0,...,9}

  A) ε

  B) +

  C) -

  D) 0...9

  E) .

  F) 0...9

  G) 0...9

  H) 0...9

  I) ε