[Automaten]Automat aus zwei Automaten basteln

Wissenschaft Informatik
#1

Hallöchen,
Ich will nen Automaten A* aus zwei Automaten bauen.
Er soll eine Wortkette(x0, x1, x2 … xn) genau dann akzeptieren, wenn die gerade-indizierten Wörter von Automat A und die ungeraden von Automat A’ akzeptiert werden.

Ich hab mich schon dran versucht, aber irgendwie kommt bei mir nur mist zustande, besonders bei den Übergangsfunktionen
(Q = Zustände, E = Symbole, P = Funktionen, q0 = Start, F = Finalzustände)

A = {Q, E, P, q0, F}
A’ = {Q’, E’, P’, q0’, F’}

Der neue Automat:
A* = {Q*, E*, P*, q0*, F*}

Q* = {Q U Q’}
E* = {E U E’}
P* = {…}

oder

Q* = {q0, q1}
E* = {xo, x1, … xn}
P* = {q0 -> q1: (x * P) in F , q1 -> q0: (x * P’) in F’}
q0 = {q0}
F = {q0, q1}

Danke!

#2

Hallo,

Ich will nen Automaten A* aus zwei Automaten bauen.

dann mal los! :smile:

Er soll eine Wortkette(x0, x1, x2 … xn) genau dann
akzeptieren, wenn die gerade-indizierten Wörter von Automat A
und die ungeraden von Automat A’ akzeptiert werden.

Das ist ziemlich einfach, wenn du zunächst einmal nicht-deterministische Automaten mit Epsilon-Übergängen zulässt. Dann brauchst du die beiden Automaten ja nur „kreisförmig“ hintereinander anordnen, Ein- und Ausgänge passend verbinden und Start- und Finalzustänge bestimmen. Genauer gesagt besteht der neue Automat dann aus der Vereinigung der Zustände, Symbole und Übergänge von A und A’ und hat zusätzlich:

  • q0 als Startsymbol

  • Epsilon-Übergänge von F nach q0’ und von F’ nach q0

  • q0 und q0’ als Finalzustände (oder alle bisherigen Finalzustände; wegen der Epsilon-Übergänge läuft das auf dasselbe hinaus)

(Ich habe dazu die beiden Ausgangsautomaten jeweils als Blackbox grafisch dargestellt und daraus den zusammengesetzten Automaten konstruiert. Die formale Darstellung überlasse ich vorerst dir.)

Anschließend kannst du, falls nötig, mit den bekannten Algorithmen die Epsilon-Kanten entfernen oder den Automaten deterministisch machen.

Viele Grüße

Andreas