0 Daumen
269 Aufrufe

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?

Avatar von

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?

1 Antwort

0 Daumen
 
Beste Antwort
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.
Avatar von

ah, das erscheint mir einleuchtend :)

vielen Dank!

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community