Beweis das jeder deterministischer Automat der diese Sprache akzeptiert mindestens 2^N Zustaende hat

Hi,

ich habe folgende Sprache:

$N\ge2$

$L\_N = \{a\_1...a\_n\in\{0,1\}^* \vert n\ge N, a\_{n-N+1}=1\}$

Nun moechte ich beweisen das jeder deterministische Automat der diese Sprache akzeptiert mindestens 2^N Zustaene hat.
Meine Idee ist irgendwie zu sagen dass das Eingabealphabet nur aus zwei Zeichen besteht und somit fuer ein N mindestens 2^N unterschiedliche Kombinationen geprueft werden muessen. Aber irgendwie weiss ich nicht ob der Ansatz total falsch ist Jemand eine Idee?

mfg

otze

Mach die Annahme: es reichen weniger als 2^N Zustände.
*Finde dann 2 unterschiedliche Strings mit länge N die auf den selben Zustand abbilden(kannst du eigentlich auch direkt annehmen)
*Nimm dann beide Strings und hänge jeweils ein weiteres Zeichen an.
*Betrachte die neuen Strings und zeige dass die Maschine einen Fehler macht
-> Widerspruch zur Annahme es geht mit weniger als 2^N zuständen.

Hi,

kann dir da nicht ganz folgen, Beweis durch Widerspruch verstehe ich noch. Wie soll ich zeigen das die Maschine einen Fehler macht?

otze

du kannst im ersten Schritt ein Wort konstruieren, so dass a_{n-N+2}=0 ist und es korrekt Teil der Sprache ist. Als zweites Wort nimmst du das bei dem alle Zeichen gleich dem ersten sind, nur dass bei ihm a_{n-N+2}=1 ist.

Nun biegst du das nach der Annahme so hin, dass die beiden Wörter auf den selben Zustand abbilden - das ist der schwierige Teil des Beweises(ich glaube es ist einfacher, erst zu postulieren dass 2 Wörter auf den selben zustand abbilden die dann "x" und "y" zu nennen und zu sagen, dass sie sich an mindestens einer Stelle unterscheiden(sonst wären die Wörter ja identisch), wonach du dann OBDA davon ausgehen kannst, dass sie sich an nur einer Stelle unterscheiden und dann diesen Fall betrachtest.)

Hängst du jetzt aber einen Buchstaben an, dann rücken die Zeichen an die Position a_{n-N+1} und nun hat die Maschine ein Problem: vorher hat sie die Teilwörter auf den selben Zustand abgebildet. Das heißt, wenn jetzt das neue Zeichen a_n gelesen wird, macht die Maschine für beide Wörter den selben Zustandsübergang. da sheißt sie entscheidet entweder, dass beide Wörter teil der Sprache sind, oder beide Wörter nicht Teil der Sprache sind. Und das ist der Fehler der zum Widerspruch führt.

knivil

Damit ist es nicht getan, es muss mindestens ein Automat noch angegeben werden, der auch wirklich nur 2ⁿ Zustaende hat. Kann ja sein, dass du z.B. nⁿ Zustaende benoetigst.

Jester

knivil schrieb:

Damit ist es nicht getan, es muss mindestens ein Automat noch angegeben werden, der auch wirklich nur 2ⁿ Zustaende hat. Kann ja sein, dass du z.B. nⁿ Zustaende benoetigst.

Er will doch nur zeigen, dass *mindestens* 2^N gebraucht werden. Vom Rest steht in der Aufgabenstellung nichts.

knivil

Ok, mein Fehler.

Hi,

wenn ich die Worte konstruiere, muessen die dann fuer eine spezielle Sprache sein?
Also nehme ich z.b.

$N=3$

$L_{3}$

?

HyperSonic

Wenn du es für jedes N beweisen willst, kannst du es natürlich nicht nur für ein spezielles N konstruieren. Eigentlich brauchst du die Wörter aber auch garnicht konstruieren, du musst nur zeigen das es sie geben muss und welche Eigenschaft sie haben.
Nimm zum Beispiel mal Wörter der Länge N. Es gibt 2^N viele davon. Hat ein Automat nun aber weniger als 2^N Zustände, dann müssen wenigstens 2 verschiedene Wörter der Länge N existieren, die schließlich den gleichen Zustand im Automaten ergeben. Da sie unterschiedlich sind, müssen sie sich an mindestens einer Position i unterscheiden. Nun hängen wir an beide Wörter die gleichen i-1 weiteren Zeichen an. Wiederum muss der Automat für beide Wörter den gleichen Zustand erreichen, denn er ist deterministisch. Da sich aber nun beide Wörter genau an der Stelle n-N+1 unterscheiden, können nicht beide in der Sprache L_N sein, da ist der Wiederspruch.

Edit: Position war falsch.

Danke fuer die Antwort. Ich glaube ich fange an zu verstehen wie so ein Beweis gefuehrt werden muss.