4. Formale Grammatik

Formale Grammatik

  • V

    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!

    0
  • ?

    Viel Erfolg! 🙂

    0
  • V

    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={S→ASB;S→5;S→ϵ;A→3;B→7;A→AA;A→ASB;B→BB;B→ASB}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?

    0
  • ?

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

    0
  • ?

    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 😉

    0
  • V

    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?

    0
  • ?

    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!

    0
  • V

    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?

    0
  • I

    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.

    0
  • I

    vip@r schrieb:

    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?

    Nein. Versuche, das Wort 753 zu erzeugen.
    Die Regeln kannst du übrigens vereinfachen, indem du A, B und C direkt einsetzt. Also z.B. S->S357 statt S->SABC.

    0
  • V

    Wenn ich aber so probiere: S->ABS; S->ASB; S->SAB; dann müsste ich noch S->3 zur Verfügung stellen und es geht wieder nicht mehr 😞

    Langsam bin ich echt ratlos...

    0
  • V

    Wäre das vielleicht noch so möglich:

    P={S->ε; S->357; S->537; S->753; S->S357; S->3S57; S->35S7; S->357S}

    Hm, ich denke, hier fehlen dann noch die restlichen Permutationen von S->S357; S->3S57; S->35S7; S->357S. Also quasi: S->S537; S->S753 usw. usf.

    Das kann ich ja wohl nicht alles per Regel definieren 😞 Ich würde ja dann 1+6+4*6=31 Regeln bekommen!

    0
  • ?

    Versuche Dir einmal zu überlegen, wie weit Du mit Regeln der Form "A -> BCDE" kommst... Es bleibt ja festzustellen, dass Du Teilworte entweder an Ort und Stelle fertig und korrekt bildest oder irgendwie Information mitschleppen musst. Und natürlich, dass Du nur einen endlichen Satz an Regeln für eine Grammatik definieren darfst.
    Und schau Dir auf jeden Fall nochmal an, ob Du mit den Regeln der Form "A -> BCDE" schon alles ausschöpfst, was Dir durch die Menge, aus der Du die Regeln entnehmen darfst, erlaubt ist.

    0
  • I

    vip@r schrieb:

    Das kann ich ja wohl nicht alles per Regel definieren 😞 Ich würde ja dann 1+6+4*6=31 Regeln bekommen!

    Und immernoch zu wenige, wenn du an Wörter wie 335577 denkst.

    Du solltest vielleicht zuerst nochmal nachdenken, welchen Typ die Sprache hat (https://en.wikipedia.org/wiki/Chomsky_hierarchy). Daraus ergibt sich dann auch, welche Form die Regeln der Grammatik haben müssen bzw. können.

    0
  • V

    Diese Chomsky-Hierarchie ist ja interessant, aber ich verstehe in der deutschen Wiki nicht all zu viel davon 😞 Welchen Typ von Grammatik benutze ich denn hier die ganze Zeit? Das muss ich ja anscheinend wissen... In meinen Unterlage wird aber gar nicht Typen Unterschieden...

    Momentan verstehe ich nur Bahnhof... Ich hab aber irgendwie das Gefühl, dass ich mich im Typ-0 bewege...

    0
  • I

    Die Sprache hat zumindest nicht Typ 2 (kann man leicht mit dem Pumping-Lemma zeigen), sondern also Typ 1 oder 0. Die für dich wichtige Information daraus ist, dass Regeln der Form „A → γ“ (A Nichtterminal, γ beliebig) nicht ausreichen. Du musst also irgendwo auch Regeln haben, wo auf der linken Seite mehr als nur ein Nichtterminal steht.

    Das ist auch das, was Decimad in seinem letzten Post angedeutet hat.

    0
  • V

    Ahja... Ich brauch also zur Lösung dieser Aufgabe auch solche Regeln: AA->A. (Nur als Beispiel!)

    Richtig?

    0
  • ?

    Ich versuche die ganze Zeit, dass die Einsicht von innen heraus kommt und dabei vielleicht etwas Übung beim Mengenlesen von Relationen bei rauskommt und Du nudelst jetzt die Wikipedia und die Chomsky-Hierarchie inklusive pumping lemma usw. vor 😞 Zumal ich davon ausgehe, dass das alles noch gar nicht behandelt wurde in vipers Lehre, sondern dass es dort erstmal nur um allgemeine uneingeschränkte Grammatiken geht.

    0
  • I

    Ja. Wobei auch links Terminalsymbole stehen dürfen.

    0
  • I

    Decimad schrieb:

    Ich versuche die ganze Zeit, dass die Einsicht von innen heraus kommt und dabei vielleicht etwas Übung beim Mengenlesen von Relationen bei rauskommt und Du nudelst jetzt die Wikipedia und die Chomsky-Hierarchie inklusive pumping lemma usw. vor 😞 Zumal ich davon ausgehe, dass das alles noch gar nicht behandelt wurde in vipers Lehre, sondern dass es dort erstmal nur um allgemeine uneingeschränkte Grammatiken geht.

    Die Einsicht, welche Formen von Regeln ausreichen, kommt aber nicht, wenn man nicht weiß, dass es überhaupt Unterschiede in der Effektivität von Regeln gibt. Die von mir nebenbei eingeworfenen Begriffe sollten in der Hinsicht zum Selbststudium animieren.

    0
Anmelden zum Antworten