 Reguläre Sprache beweisen |
sxcee
unregistriert
 |
|
| Reguläre Sprache beweisen |
     |
Meine Frage:
Hallo Informatiker,
ich stehe gerade vor der Herausforderung eine reguläre Sprache zu beweisen. Um es euch einfacher zu machen kopiere ich die Aufgabenstellung:
Sei ? = {0,1} und w ? ??. Mit |w|0 und |w|1 bezeichnen wir die Anzahl
der Nullen bzw. Einsen in w, d.h. für z.B. w := 10100010 gilt |w|0 = 5 und |w|1 = 3.
a) Sei L ? ?? die Sprache aller Wörter x, für die |x|0 und |x|1 jeweils eine der ersten 100 Primzahlen ist. Das obige w ist also in L enthalten, denn sowohl 5 als auch 3 sind Primzahlen. 10111 ist nicht in L, denn |10111|1 = 4 ist keine Primzahl. Beweisen Sie, dass L regulär ist.
Meine Ideen:
Meine Idee war, da ich gelernt habe wie man die Regularität einer Sprache mit dem Pumping-Lemma widerlegt, dieses auch auf den Beweis für die Regularität anzuwenden. Aber da stellt sich mir die Frage, ob das überhaupt möglich ist (zu umständlich) ?
Da ich die drei Eigenschaften einer regulären Sprache kenne, kann ich es auch dadurch beweisen, dass wenn eine Eigenschaft gegeben ist, dass das dann die anderen impliziert.
Ich hänge aber extrem an dem Problem einfach nicht drauf zu kommen.
In erster Linie suche ich hier einen Lösungsansatz, sodass ich sogar selbst noch auf das Ergebnis kommen kann !
|
|
13.05.2014 11:37 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Hallo,
es wäre nett, wenn Du das nächste mal Sonderzeichen, die nicht richtig dargestellt werden können, korrigierst.
Die Lösung des Problems liegt schon in der Beschreibung. Es geht um die ersten 100 Primzahlen. Es handelt sich also um eine endliche Menge von Wörtern. Naiv kannst du also einfach alle möglichen Wörter aufschreiben und für jedes Wort einen Automaten konstruieren. Somit hätten wir eine endliche Menge von regulären Sprachen. Reguläre Sprachen sind unter Vereinigung abgeschlossen. Die Sprache ist also regulär.
Sollte etwas unklar sein, bitte noch mal nachhaken,.
VG,
Karlito
|
|
|
14.05.2014 16:00 |
|
|
|
