NFA: Beweis durch zwei Mengeninklusionen |
| 13.04.2013, 12:04 | Tim1991 | Auf diesen Beitrag antworten » |
| NFA: Beweis durch zwei Mengeninklusionen -- Geben Sie einen NFA A an, der die Sprache L all jener Worte w Elemet in {0,1}* akzeptiert, bei denen die Anzahl der Nullen durch 4 und die Anzahl der Einsen durch 3 teilbar ist (jeweils ohne Rest, d.h. ein Wort w soll genau dann akzeptiert werden, wenn |w|0 ein Vielfaches von 4 und |w|1 ein Vielfaches von 3 ist). Zeigen Sie, dass ihr Automat das gewünschte leistet, indem Sie zwei Mengeninklusionen beweisen. -- Den ersten Teil der Aufgabe habe ich durch eine Zeichnung gelöst. Nun weiß ich aber nicht, was bei dem Beweis genau gewollt ist. Mir ist klar, was eine Mengeninklusion ist, aber bisher kenne ich das nur, wenn ich zwei Mengen druch verschiedene Gleichungen ausgedrückt werden, wie zB (U°V)*U=U°(V°U)* Aber hier sehe ich nicht mal die Menge. Muss ich beweisen {0,1}* ist Teilmenge von {0,1}* und andersherum? Falls ja, wie fange ich das an? |
||
| 13.04.2013, 18:50 | chrizke | Auf diesen Beitrag antworten » |
Also du hast die Sprache L und den Automaten A mit dessen Sprache L(A) und sollst zeigen, dass . Dazu nimmst du die "Technik" der Mengeninklusion und zeigst dann: Die Sprache L ist in L(A), also wird von A erkannt. Dazu zeigst du, dass der Automat Wörter akzeptiert, deren Anzahl an Nullen durch 4 und die Anzahl der Einsen durch 3 teilbar ist. Dass er evtl. auch noch andere akzeptiert ist hier nicht relevant. Hier gehts genau umgekehrt. Hier musst du zeigen, dass wenn der Automat ein Wort akzeptiert, dieses dann die Forderungen an die Teilberkeit der Häufigkeiten erfüllt. |
||
| 13.04.2013, 19:33 | chrizke | Auf diesen Beitrag antworten » |
Ich habe den Automaten auch mal konstruiert. Den direkt zu benutzen, um die Gleichheit zu zeigen, halte ich für etwas umständlich – eine Fleißaufgabe. Man muss schon über die Konstruktion argumentieren. Bei meiner Konstruktion bin ich so vorgegangen, dass ich erst je einen Automaten für die einzelnen Teilbarkeitsforderungen aufgestellt und diese dann geschnitten habe, um den finalen Automaten zu erhalten. Mit dieser Konstruktion ließe sich leichter über die Mengeninklusion argumentieren, falls ihr schon gelernt habt, wie man den Schnitt aus Zwei Automaten erstellt. Eine weitere Möglichkeit wäre, in den Zuständen "Counter" zu benutzen, die bestimmen, wann bei beiden Buchstaben die Teilbarkeit erfüllt ist. Dann könnte man die Inklusionen auch ohne Umwege beweisen. Beide Wege sind natürlich gleichwertig und ich habe gemerkt, dass, wenn man die Notation richtig wählt, beide Automaten auch von der Zustandsbeschriftung her gleich sind. Am Ende ist es dann lediglich eine Frage der Konstruktion, wie du im Beweis für die eigentliche Aufgabe argumentieren kannst. |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
