Formale Grammatik



  • Hi Leute!

    Ich soll eine formale Grammatik erstellen, die mir alle Binärzahlen erzeugen kann, die durch 8 teilbar sind. Ich hab mir natürlich schon Gedanken dazu gemacht:

    Die Grammatik muss ja angegeben werden, weshalb ich mir folgende Ausgangsbasis überlegt habe:

    G=(V,,P,S)G=(V, \sum, P, S), sowie den Nichtterminalen V={A,B}V=\{ A, B \} und den Terminalen {0,1}\sum \{0,1\}. Des Weiteren braucht man ja noch bestimmte Produktionsregeln: P={SAB,A100,B0,BB}P=\{S \to AB, A \to 100, B \to 0, B \to B\}.

    Aber genau bei diesen Produktionsregeln liegt nun der Hase im Pfeffer. Darf ich die so schreiben? Insbesondere das BB}B \to B\} macht mir Magenschmerzen. Was sagt ihr? Kann mir jemand weiterhelfen?



  • Welchen Typ soll die Grammatik haben?



  • Typ? Ich wusste bis jetzt nicht, dass es auch unterschiedlichen Typen geben soll! Auch in meine Vorlesungsunterlagen steht nix zu typen?!?!?

    Ich hab übrigens nochmal neu angefangen:

    V={S}V=\{S\}, ={0,1}\sum=\{0,1\}, P={S1S00,SS0,S0S,S0}P=\{S \to 1S00, S \to S0, S \to 0S, S \to 0\}

    Hier hab ich zwar jetzt mittlerweile jede mögliche durch 8 teilbare Binärzahl generiert, aber das Problem, dass mit der Produktion [latex]S \to 0S \to 01S00 \to 01000[/latex] leider auch führende Nullen produziert werden könne, was ich aber nicht darf 😞

    Ich glaub das hab ich im ersten Beitrag vergessen reinzuschreiben.

    Edit: Zusätzliche Frage: Oder ist diese Grammatik nun korrekt, da als erste Ableitungsregel das S0SS \to 0S nicht benutzt werden darf, sondern wirklich das erste ('linkeste' Element) in der Produktionsmenge benutzt werden muss? Wobei nach diesem Element die Reihenfolge welche Regel man benutzt egal ist?



  • Nun ich meinte, welche Bildungsregeln sind erlaubt?



  • Also, geht sowas?

    S->0; S->1000; S->1B000; B->0; B->1; B->BB;

    Drei Regeln für S, weil ich nicht noch einen extra nichtterminal einführen wollte.



  • Ah, ok. Jetzt weiß ich was du meinst:

    P((V)+×(V))P \subseteq ((V \cup \sum)^{+} \times (V \cup \sum)^{*})

    Das ist das was du wahrscheinlich wissen wolltest. Ich hab übrigens meinem Eintrag eins drüber noch eine Frage hinzugefügt.



  • Noch besser! Dann kann man auch auf das leere Symbol abbilden!

    S->0; S->1B000; B->leer; B->1; B->0; B->BB



  • Also die Regeln haben keine Anwendungsreihenfolge oder irgendeine Präzedenz.



  • Danke Decimad!

    Du hast mir sehr geholfen!

    Jetzt hätte ich noch eine Frage: Wenn ich nun diese Produktionsregeln habe S->0; S->1B000; B->leer; B->1; B->0; B->BB, dann muss ich mit einer der drei Regeln für das Startsymbol S beginnen. Welches ich davon nehme ist egal; es muss ja sowieso immer eine durch 8 teilbare Zahl ohne führende Nullen rauskommen, richtig?



  • Oh, deine Antwort hat sich mit meiner erneuten Frage überschnitten. Naja, Reihenfolgt doch irgendwie schon, oder? Ich darf ja erst B->BB anwenden, wenn im vorherigen auch ein B drin war, oder? Das wiederum bedeutet, dass ich zu einem B komme, muss ich eine der Regeln anwenden die von S auf "irgendwas" abbilden.



  • Wichtig ist, dass egal welchen "Pfad" von Regeln du wählst, dass wenn du bei einem Wort landest, das nur noch Terminale besitzt, dieses Wort eine Zahl darstellt, die durch 8 teilbar ist. Wir garantieren mit den Regeln, dass die gebildeten Worte entweder 0 sind, oder mit drei Nullen aufhören, dann aber vorne keine 0 haben.
    Ich weiß nicht, ob ich Deine Frage gerade richtig verstehe. Vielleicht nochmal anders formulieren, wenn das da oben es nicht aufklärt.

    @Edit: Am Anfang steht immer das in der Grammatik festgelegte S da. S wird mit den Regeln dann zu allen Wörtern der Grammatik expandiert (Daher kann als allererste Regel nur eine solche gewählt werden, die das S in irgendetwas abbildet).



  • Ja, ich denke, ich hab das durch dich jetzt gut verstanden. Es gibt keine Reihenfolge. Das ist schon mal gut so.

    Und dein Edit, hat's dann komplett durchsichtig für mich gemacht:

    @Edit: Am Anfang steht immer das in der Grammatik festgelegte S da. S wird mit den Regeln dann zu allen Wörtern der Grammatik expandiert (Daher kann als allererste Regel nur eine solche gewählt werden, die das S in irgendetwas abbildet).

    Ich denke, ich hab das jetzt soweit gerafft und ich mach mich dann mal gleich noch an eine zweite ähnliche Aufgabe!

    DANKE!



  • Viel Erfolg! 🙂



  • Vielleicht magst du dir die Aufgabe auch nochmal kurz angucken?

    Entwerfen Sie eine Grammatik, die die folgende Sprache erzeugt:

    L = \{ w | w \in \{ 3,5,7 \}^{*}, \text{w enthält die Ziffern 3,5 und 7 gleich oft} \}

    Meine Lösung:

    G=(V,,P,S)G=(V, \sum, P, S), ={3,5,7}\sum=\{3,5,7\}, V={S,A,B}V=\{S, A, B\}, P={SASB;S5;Sϵ;A3;B7;AAA;AASB;BBB;BASB}P=\{ S \to ASB; S \to 5; S \to \epsilon; A \to 3; B \to 7; A \to AA; A \to ASB; B \to BB; B \to ASB \}

    Kommst du auf das gleiche? Stimmt meine Lösung?



  • Okay, ich wähle die Regel S->5. Ergebnis: "5". Jetzt bist Du dran!



  • Ich könnte mir vorstellen, dass Du jetzt gerade brütest, und zwar nicht weil Du gerade nicht auf den richtigen Regelsatz kommst, sondern aus einem anderen Grund. Wenn Du magst, melde Dich einfach 😉



  • Hm, du hast natürlich Recht, dass diese REgel dann gleich mal blödsinn ist, da sie die 3 und 7 vernachlässigt...

    Irgendwie kommt mir auch die Regel S->ASB mittlerweile komisch vor, da ich hier dann zwar gleich vielen 3en und 7en kommen kann, die 5en aber nicht mehr gleich viel werden. Ich denke du weißt was ich meine.

    Vielleicht kannst du mir ja wieder ein bisschen helfen?

    Edit: Was aber auf jeden Fall stimmen muss, sind die folgenden Regeln:

    S->ASB; A->3; B->7

    Jetzt ist nur noch das S in der Mitte das Problem...

    Edit2: Jetzt glaub ich hab ich's!

    P={S->ε; S->ABC; S->SABC; S->ASBC; S->ABSC; S->ABCS; A->3; B->5; C->7}

    Simmt doch, oder?



  • Du hast es schon genau richtig erkannt. Man bekommt von 2 Zeichen die gleiche Anzahl hin (aber stimmt das auch noch für beliebige Reihenfolgen?). Ab 3 setzt es aus. Wie Du es drehst und wendest, du wirst die Sprache nicht mit diesem Muster von Regeln bilden können.
    Daher schaue Dir noch einmal ganz genau an, wie die Menge aussieht, aus der man die Regeln in Deinem Aufgabenfall entnehmen darf!



  • Sorry, Edit hat sich überschnitten 😞

    P={S->ε; S->ABC; S->SABC; S->ASBC; S->ABSC; S->ABCS; A->3; B->5; C->7}

    Simmt doch, oder?



  • vip@r schrieb:

    Edit: Was aber auf jeden Fall stimmen muss, sind die folgenden Regeln:

    S->ASB; A->3; B->7

    Jetzt ist nur noch das S in der Mitte das Problem...

    Die Wörter sollen 3, 5 und 7 gleich oft enthalten. Seien also n3, n5 und n7 die Anzahl der 3en, 5en und 7en im jeweiligen Wort. Dann muss also für alle Wörter, die aus S ableitbar sind, gelten: n3 = n5 = n7.
    Nun kann ich mit den gegebenen Regeln 3S7 ableiten. Damit daraus ein Wort wird, das in der Sprache liegt, muss für alle Wörter, die aus S ableitbar sind, gelten: n3 = n5+1 = n7.
    Diese beiden Aussagen stehen im Widerspruch. Also sind diese Regeln, auch partiell, schonmal falsch.


Log in to reply