Was passiert bei $n>m$?

Question

Was würde passieren, wenn n größer als m wäre? Dann gäbe es ja z.B. eine Situation $(s_1, d, k_0)$, die nicht definiert wäre, wobei wir uns ja in einem Endzustand befinden. Das wäre dann ungültig, weil kein  entsprechender Zustandsübergang definiert ist, unabhängig davon, dass man sich schon in einem Endzustand befindet, oder? Das ist mir grad noch nicht ganz klar. Sonst waren es ja meistens Fälle, in denen ich mich bei ungültigen Wörtern nicht "weiterbewegen kann", während ich mich in einem Nicht-Endzustand befinde. Danke schonmal!

Answer 1

Damit ein Wort von einem Kellerautomaten akzeptiert wird, müssen 2 Bedingungen erfüllt sein:

- 1. Das Eingabewort ist vollständig abgearbeitet.

- 2. Der Kellerautomat befindet sich in einem Endzustand.

In dem von dir geschilderten Fall ist der KA zwar in einem Endzustand, aber das "d" könnte mangels eines passenden Übergangs nicht verarbeitet werden -> Bedingung 1 nicht erfüllt, Wort wird nicht akzeptiert.

Tobias (Tutor)