Theratische informatik - automaten

Wissenschaft Informatik
#1

Hallo,
es ist ein Automat A gegeben.
Jetzt soll ein Automat B erstellt werden, der die wörter A nicht akzeptiert. B\L(A)

frage: kann Automat B beliebig aussehen, hauptsache er darf kein wort des Automaten A akzeptieren?

zb. (ganz kleiner Automat) regeln von A:
S-> aX,bX
X->Ya,Yb,Yc
Y->d

dann wären die Regeln von Automat (als Beispiel, könnte auch anders aussehen) B:

S-> cX
X->Ya,Yb,Yc
Y->d

oder (mit anderen regeln)
zb.
S-> aX,bX
X->Ya,Yb,Yc
Y->e

stimmt es?
also es darf nur kein wort von Automat A akzeptiert werden?

vielen dank

#2

Hallo leo,

es ist ein Automat A gegeben.
Jetzt soll ein Automat B erstellt werden, der die wörter A
nicht akzeptiert. B\L(A)

Frage: Soll B tatsächlich nur die Wörter aus L(A) nicht akzeptieren (und der Rest ist egal), oder soll B das Komplement von L(A) akzeptieren, d.h. ein Wort w verwerfen, genau dann wenn w ∈ L(A) und anderenfalls akzeptieren?

Im ersten Fall reicht ein Automat, der nur die leere Menge akzeptiert, also ein Automat ohne Endzustände.
Falls aber das Komplement akzeptiert werden soll, bildet man B aus A am besten dadurch, dass Regeln und Zustandsmenge von A übernommen werden und die Menge der Endzustände invertiert wird. Dann führt jede Eingabe, die A in einen Endzustand überführt, B in einen nicht akzeptierenden Zustand und umgekehrt.

Gruß,
Ralf