Endliche Automaten

Id: auto.tex,v 1.4 2005/10/19 22:19:55 waldmann Exp

Intern stellt man reguläre Sprachen lieber effizienter dar:

Ein (nichtdeterministischer) endlicher Automat A ist ein Tupel (Q, S, F, T) mit

  • endlicher Menge Q (Zustände)
  • Menge S $ \subseteq$ Q (Start-Zustände)
  • Menge F $ \subseteq$ Q (akzeptierende
    Zustände)
  • Übergangs-Relation T $ \subseteq$ (Q×$ \Sigma$×Q)
autotool:
NFA { alphabet = mkSet "ab"
  , states = mkSet [ 1, 2, 3]
  , starts = mkSet [ 2]
  , finals = mkSet [ 2]
  , trans = collect
    [ (1, 'a', 2)
    , (2, 'a', 1)
    , (2, 'b', 3)
    , (3, 'b', 2)
    ]
  }



Johannes Waldmann 2006-02-02