Automaten in Source Code

[JasonDX]

Eine (IMO sinnvolle(re)) OOP-Lösung wäre folgender Aufbau:

Delphi-Quellcode:

TDFAState = class;
TDFA = class
public
  property Alphabet: array of TToken; read;
  property StartState: TDFAState; read;
  property States: array of TDFAState; read;

  function Accepts(word: array of TToken): boolean;
end;

TDFAState = class
protected
  Transitions: TDictionary;
public
  propterty TDFA Owner; read;
  property IsFinalState: boolean; read;
  procedure Map(Targets: array of TDFAState); //Setzt Transitions (einmalig)
  function Transition(Token: TToken): TDFAState;
end;

//Manche Methoden:

function TDFA.accepts(word: array of TToken): boolean;
var
  CurrentState: TDFAState;
  i: integer;
begin
  CurrentState := self.StartState;
  for i := 0 to high(word) do
    CurrentState := CurrentState.Transition(word[i]);
  result := CurrentState.IsFinalState;
end;

procedure TDFAState.Map(Targets: array of TDFAState);
var
  i: integer;
begin
  if (Transitions = nil)
  begin
    Transitions := Dictionary.Create();
    for i := 0 to high(Owner.Alphabet) do
      Transitions.Add(Owner.Alphabet[i], Targets[i]);
  end;
end;

function Transition(Token: TToken): TDFAState;
begin
  if (not Transitions.Contains(Token))
    raise Exception.Create('Received Token not included in Alphabet');
  result := Transitions[Token];
end;

Gemacht wird das ganze dann so, dass im Konstruktor von TDFA:
1. Alle Zustände erstellt werden (sodass sie über TDFA.States verfügbar sind)
2. Alle Zustände eine Liste von Zuständen bekommen. Dabei gilt: Mit dem 1. Token des Alphabets kommt man in den 1. Zustand in der Liste. Ein Beispiel:

Delphi-Quellcode:

constructor TDFA.Create(...)
begin
  //Create States...
  //Map States
  States[0].Map([States[0], States[1], States[1]]);
  States[1].Map([States[2], States[0], States[0]]);
  States[2].Map([States[1], States[2], States[1]]);
end;

Syntaxmäßig gebe ich keine Garantie, auch ist der Klassenaufbau teilweise nur skizziert. Aber es dürfte für ein Verständnis der Idee reichen
Dictionary wusst ich jetzt nicht, ob/welche Klasse in Delphi dieses .NET-Äquivalent implementiert. Es ist jedenfalls einfach nur ein Mapping von TToken auf TDFAState.
Btw: Diese OOP-Variante hat den Vorteil, dass Bearbeitungsoperationen auf dem DFA implementiert werden können.

greetz
Mike