Automaten in Source Code

[Christian18]

Hallo,

ich beschäftige mich gerade mit Automaten. Ich habe gelernt viele Probleme damit zu lösen, die ich vorher noch nicht lösen konnte. Nun wollte ich mich damit beschäftigen, meine Ideen in Quellcode umzusetzen. Hat jemand eine Idee, wie mach das machen kann?

Vieleicht hat jemand auch ein kleinen Beispielautomat mit Source Code.

Vielen Dank im vorraus.

MfG Christian18

[Codewalker]

Ich gehe mal davon aus, du meinst einen endlichen Automaten. Prinzipiell ist es eine verschachtelte Case-Abfrage. Die äußere fragt ab, in welchem Zustand der Automat sich gerade befindet und jede innere fragt ab, welche Transition gewählt werden muss.

Ein Automat mit 3 Zuständen (q0,q1,q2) und einem Alphabet 'a' und 'b' wäre dann prinzipiell z.B. so:

Delphi-Quellcode:

{...}
case AktuellerZustand of
 q0:  case Zeichen of
      'a': // Führe Transition von q0 aus, wenn ein a gelesen wird
      'b': // Das gleiche für b
     end;
 q1:  case Zeichen of
      'a': // Führe Transition von q1 aus, wenn ein a gelesen wird
      'b': // Das gleiche für b
     end;
 q2:  case Zeichen of
      'a': // Führe Transition von q2 aus, wenn ein a gelesen wird
      'b': // Das gleiche für b
     end;
end;

[Christian18]

Hallo,

vielen Dank für deine Antwort. Wie Automaten funktionieren, habe ich verstanden. Ich lese immer nur bezüge auf ein Alphabet. Die Beispiele die ich habe nutzen auch immer nur das Alphabet. Kann es sein, das man Automaten nur in Kombination mit Strings verwenden kann?

So den richtigen Sinn habe ich glaube noch nicht so wirklich verstanden. Meiner Meinung nach würde ich sagen, kann ich Probleme auch mit weniger SourceCode lösen. Wozu dient also dieses "Konzept"?

MfG Christian18

[himitsu]

Strings werden wohl nur zufällig genommen

im Prinzip ist ein Zeichen/Char auch nur ein ordinaler Typ und man könnte stattdessen auch jeden anderen ordinalen Typen nehmen

Delphi-Quellcode:

while ... do
  case zustand of
    z0: case wert of
          w1: ...;
          w2: ...;
          ...
        end;
    z1: case wert of
          w1: ...;
          w2: ...;
          ...
        end;
    z2: case wert of
          w1: ...;
          w2: ...;
          ...
        end;
    ....
  end;

[Christian18]

Ich bin gerade noch ein bisschen am überlegen, ob man folgendes Problem mit Automaten lösen könnte.

Ich habe einen String:

123;321;keine_ahnung

Der Automat soll diesen String nun auseinander nehmen. Genau an den stellen, so die ; sind.

Also habe ich einen Start Zustand q0. In diesem soll er immer bleiben, wenn kein ; kommt.

Wenn ein ; kommt, dann soll er in den Zustand q1 wechseln. Der Theorie ist ja gar nicht so schwierig. Also müsste das eigentlich mit Automaten funktionieren. Aber wie würde das in SourceCode aussehen.

MfG Christian18

[SebE]

boah, war schon ewig nicht mehr hier - ich versuchs mal:

Delphi-Quellcode:

type
  zustant = (q0, q1);

var
  i, sLen: integer;
  s: zustand;
  b, r: string;

begin
i := 1;
sLen := length(b);
s := q0;
r := '';

while (i <= sLen do) begin
    case s of
    q0: begin
      if b[i] = ';' then
        s := q1
      else r := r + s[i]
      end;
    q1: begin // ";" gelesen
      writeln(r);
      r := '';
      s := q0
      end
    end;

  i := i  + 1
  end;

[SebE]

Das obige Beispiel (kann Fehler beinhalten) zeigt - ich nenn's mal - die "direkte" Möglichkeit mit Automaten zu arbeiten.

Eigentlich ist jedes Program ein Automat (man siehts es nur nicht auf den ersten Blick):
Nimm alle Variablen, die du verwendest zusammen - diese ergeben deinen "Zustand", dein Programm reagiert dann in Abhängigkeit dieses Zustandes.

Wenn man Rekursionen einbaut muss man den Stack-Inhalt (inkl. die Tiefe der Rekursion) als Teil des Zustandes zählen.
Hier sind wir dann schnell bei Parsern (Compilerbau) angelangt.

Damit kannst du dann "richtige" Grammatiken verwenden.

Deine (einfache) Grammatik sah so aus:
start ::= Text {";" Text}.
Text ::= { <alle Zeichen> }.

Mit Rekursionen geht auch folgendes ganz leicht:
Start ::= Anweisung.
Anweisung ::= Schleife1 | Schleife2 | ... .
Schleife1 ::= "REPEAT" Anweisung "UNTIL" Ausdruck.
Schleife2 ::= "WHILE" Ausdruck "DO" Anweisung.
...

Wollt ich einfach nochmal anbringen - mich interessiert das Thema Automaten (und Parserbau) auch :-)

[JasonDX]

Zitat:

Zitat von SebE

Eigentlich ist jedes Program ein Automat

Wenn wir von regulären Automaten sprechen, ist das nicht richtig. Reguläre Automaten sind deutlich ausdrucksärmer als Programme/Turingmaschinen/Lamdaterme.
Als Beispiel: Kein regulärer Automat dieser Welt kann x*x ausrechnen (Beweisbar durch Myhill-Nerode).

greetz
Mike

btw, zum Topic: Ein Theoretiker würde den Automaten in eine Regex umwandeln, und dann dafür existierende Funktionen verwenden :D

[alzaimar]

Mit Case würe ich das nie und nimmer machen: Viel zu umständlich und zu unübersichtlich.
Ich mache das so:
1. Eingabealphabet definieren
2. Zustandsgraph aufzeichnen
3. Zustände durchnummerieren.
4. Zustandsübergangstabelle erstellen (Spalten = Alphabet, Zeilen = Zustände aus (3))

Delphi-Quellcode:

Procedure DEA (aInput : TAlphabetStream);
Begin
  State := START;
  While Not (State in [ERROR, STOP]) Do
    State := DEA[State, NextToken(aInput)];
    ProcessState(State);
  End;
  If State = ERROR Then
    ShowError
  else
    Success;
End;

Damit lassen sich dann alle DEAs dieser Welt abarbeiten.

[SebE]

Das mit der Automatentabelle ist auch eine gute Idee (wie's bei Bottom-Up-Parsern gemacht wird).
Muss man abwägen (Gesachmackssache).

Ich finde die Case-Variante übersichtlicher und EVTL. auch schneller erweiterbar.
Die Tabelle wird in manchen Fällen einfach nur (physikalisch) groß (Beispiel: viele Zustände mit dem gleichen Verhalten).

@JasonDX:

Zitat:

Wenn wir von regulären Automaten sprechen, ist das nicht richtig.

Ich hab mich aber nicht auf DEAs festgelegt ;-)