Endliche Automaten

Id: auto.tex,v 1.3 2004/12/14 12:36:40 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)
• Relation T $\subseteq$ (Q×$\Sigma$×Q)

  bzw. Funktion T : (Q×$\Sigma$)$\to$2^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)
    ]
  }