Reguläre Sprache Theoretische Informatik?
Wahr oder Falsch: Sei Σ = {0, 1} und sei L ⊆ Σ∗ regulär. Sei L′ die Sprache, die man aus L erhält, indem man in jedem Wort aus L jedes zweite Vorkommen von 0 durch 10, und jedes dritte Vorkommen von 1 durch 01 ersetzt. Dann ist L′ regulär. Begründen Sie Ihre Antwort.
1 Antwort
Versuch doch einen Automaten zu konstruieren, der L' annimmt, indem du den Automaten, der L annimmt umbaust.
Meine Idee wäre, dass du Die Zustandsmenge Qx{0, 1}x{0,1,2} Vereinigt mit einer Menge von Sonderzuständen, die du selbst wählen musst, wobei der Zustand (q_i, m, n) bedeutet, dass du dich bei dem Automaten L im Zustand qi befinden würdest, und dass m die Anzahl der 0en (Mod 2) und n die Anzahl der 3en (Mod 3) ist.
Die genaue Vernetzung des Automaten überlegst du dir bitte selbst.