Formale Grammatik
-
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!
-
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.
-
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.
-
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...
-
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.
-
Ahja... Ich brauch also zur Lösung dieser Aufgabe auch solche Regeln: AA->A. (Nur als Beispiel!)
Richtig?
-
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.
-
Ja. Wobei auch links Terminalsymbole stehen dürfen.
-
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.
-
Nochmal ein versuch: S->SABC; S->ASBC; S->ABSC; S->ABCS; SA->A; AS->A; BS->B; CS->C; SB->B; SC->C
Richtig? Gefühlsmäßig nein...
-
Also ich halte es nicht für abwegig, dass man nach etwas Überlegung auf die Idee kommt, dass Regeln der Form A->BCD sehr beschränkend wirken. Daher habe ich die ganze Zeit die Hintertür offen gehalten, dass es ja noch mehr geben könnte.
So ist es doch in der Lehre. Man schaut sich die Sachen erstmal allgemein an, bildet eine gewisse Intuition, macht vereinzelte Beobachtungen und arbeit das dann formal auf. Aber wenn man in Phase 1 schon mit den Ergebnissen von Phase 3 konfrontiert wird, ist die Chance irgendwie vertan und man wird zudem noch mit soviel Stoff überwältigt, dass es erstmal wieder Zeit kostet, da Land zu sehen. Ich halte nichts davon, aus der Wikipedia zu lernen - wenn man denn überhaupt lernen will. Zum Nachschlagen von Fakten, die man nur kurz als Mittel zum Zweck braucht, taugt sie natürlich außerordentlich gut.
-
Leute streitet euch bitte nicht. Da ist mir nicht geholfen
Ich brüte noch immer über der Aufgabe...
Mittlerweile bin ich auch noch auf das hier gekommen:
S->SA; S->AS; S->SBC; S->BSC; S->SCB; S->CSB; S->A; S->ε
Das geht aber auch nicht. Siehe Beispiel: S->BSC->BBSCC->???
Egal was ich nun für S einsetze, komm ich nicht mehr auf passende Anzahl von A...
-
Nun, das kann ja eventuell bedeuten, dass man entweder einen verflucht komplizierten Kniff braucht, oder aber, dass es mit dieser Form von Regeln einfach nicht möglich ist, die Sprache zu bilden.
Edit: Ich meine explizit diese Form von Regeln, die du im letzten Post benutzt hast, nicht die Menge der Regeln, die du auf der ersten Seite angegeben hast.
-
Hm, Decimad. Willst du nun damit sagen, dass die Aufgabe mit meinem Wissen über formale Grammatiken nicht lösbar ist? Ich brüte nämlich immer noch bzw. schon wieder über derselben Aufgabe...
Könntest du mich vielleicht etwas mehr aufklären? Ist es überhaupt möglich eine passende Grammatik anzugeben, oder ist nur MIR nicht möglich eine Grammatik anzugeben?
-
Nochmal. Der letzte Versuch meiner Seite. Dann gebe ich auf:
P={
S->ε,
S->SABC, S->ASBC, S->ABSC, S->ABCS,
S->SACB, S->ASCB, S->ACSB, S->ACBS,
S->SCAB, S->CSAB, S->CASB, S->CABS,
S->SCBA, S->CSBA, S->CBSA, S->CBAS,
S->SBCA, S->BSCA, S->BCSA, S->BCAS,
S->SBAC, S->BSAC, S->BASC, S->BACS,
A->3, B->5, C->7
}Stimmt's?
-
Wozu braucht man den Quatsch? Unsere Informatiker machen ganz normale Programmieraufgaben und verdienen noch nicht mal mehr als wir. So wie ich gehört habe sind 99% der Informatiker bloß als Codemonkeys eingestellt.
-
vip@r schrieb:
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} \}
Nun, ich interpretiere dass so, dass die Anzahl der 3en und 5en zusammen genauso oft vorkommen, wie die 7en. D.h. es handelt sich um eine kontextfrei Sprache. Bei einer anderen Interpretation wird es schwer fuer den Kontrolleur zu sehen, ob die kontextsensitive Grammatik auch wirklich die Sprache erzeugt. In meinem Grundstudium war es nie noetig, eine kontextsensitive Grammatik fuer eine Sprache anzugeben.
Typ? Ich wusste bis jetzt nicht, dass es auch unterschiedlichen Typen geben soll!
Omg.
-
knivil schrieb:
vip@r schrieb:
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} \}
Nun, ich interpretiere dass so, dass die Anzahl der 3en und 5en zusammen genauso oft vorkommen, wie die 7en.
Das halte ich für ne recht gewagte Interpretation. Sicherlich kann man das noch klarer hinschreiben, aber ich würde hier schon absichtliche Fehlinterpretation unterstellen. Wenn ich sage: "Male die Autos auf dem Bild jeweils in einer Farbe an und verwende die Farben rot, grün, gelb und blau dabei gleich oft", dass ich haben will, dass Du genauso viele blaue Autos produzierst wie rote, grüne und gelbe zusammen?
-
Leider kann ich nicht den Prof. fragen, dass muss jemand anders machen.
-
Wäre eine nicht-kontextfreie Grammatik denn so schwer? Mal von der Grundidee: Ich erzeuge mit ein paar Regeln die Sprache (357)*, dann hab ich noch
dreisechs Regeln für alle Vertauschungen zweier nebeneinanderliegender Zeichen, also der Art 35 -> 53.