Wenn es für L einen endlichen Automaten gibt, gibt es auch für jede Teilmenge von L einen?

Question

Es ist eine Sprache L gegeben, welche durch einen endlichen Automaten entscheidbar ist. Gibt es dann auch einen endlichen Automaten jeweils für jede Teilmenge von L?

Comments

Sagen wir, L={a}*. Dafuer gibt es bestimmt einen endlichen Automaten. Nun betrachten wir L', das nur solche Woerter aus L enthaelt, deren Laenge eine Primzahl ist. Ob es dafuer auch einen endlichen Automaten gibt? Was meinst Du?

Answer 1

Ich glaube nicht.
Wenn du über {a,b} die Sprache nimmst, die mit
beliebig vielen a's beginnt und wiederum mit beliebig vielen b' s
gefolgt von einem a endet, dann kann man die ja leicht durch
einen endlichen Automaten mit drei Zuständen beschreiben.

Wenn aber die Bedingung dazukommt, das diese
"beliebig vielen " bei a und b die gleiche Anazhl sein soll,
da geht das wohl mitb einem endl. Aut. nicht.

Comments

ah, das erscheint mir einleuchtend :)

vielen Dank!