Abschlusseigenschaften / Grammatiken |
| 05.03.2012, 16:20 | Auf diesen Beitrag antworten » | ||||||
| earthhero | Abschlusseigenschaften / Grammatiken Hey Leute, ich hoffe nicht, dass ich Euch durch meine blöde Fragerei nerve, aber mir fehlt einfach der Klick im Kopf... ich habe Mal zwei, wohl vermutlich, Recht einfache Fragen. Wofür sind die Abschlusseigenschaften gut? Was bewirken die? Und was muss ich auf die Fragen "Was sind Abschlusseigenschaften" antworten?! Dann kommen wir zu den Grammatiken, wenn ich als Fragen bekomme "Schreiben Sie eine Grammatik für Typ 2 auf" Was muss dann da stehen?! Einfach nur, dass auf der linken Seite max/min 1 Nichterminale stehen darf und die rechte Seite relativ egal ist?! Die Grundlagen, sprich die Oberflächen der Theo Inf verstehe ich so langsam, allerdings wenn ich tiefer geht wie "Woran erkennt man eine kontexsensitive/kontexfreie... Grammatik, steh ich meist auf dem Schlauch da ich nicht weiß ich ich das zeigen bzw. erklären kann...sprich in welchen Typen diese liegen, wie diese erkannt werden weiß ich. Am 14.03. habe ich die Prüfung, bis dahin müsst ihr mich noch mit blöden Fragen aushalten 
LG |
||||||
|
|
|||||||
| 06.03.2012, 09:36 | Auf diesen Beitrag antworten » | ||||||
| Karlito | RE: Abschlusseigenschaften / Grammatiken
Kennst du die Abschlusseigenschaften aus der Mathematik? Bei den Abschlusseigenschaften der Sprachen geht es um die gleiche Sache: Bleibe ich mit diversen Operationen in der selben Klasse. Hier jedoch die Klasse der Sprachen laut Chomsky-Hierarchie. Abschlusseigenschaften: - Komplement - Kleene-Abschluss - Konkatenation - Vereinigung - Durchschnitt
Ja!
Ich würde hier die Merkmale nennen, die lt Chomsky-Hierarchie gültig sind. D.h. Definitionen Auswendig lernen. Halt wie bei der Typ2-Sprache, wie die Grammatik aussieht. Etwas anderes kann ich mir grad nicht vorstellen. VG, Karlito |
||||||
| 06.03.2012, 22:04 | Auf diesen Beitrag antworten » | ||||||
| earthhero | Ehrlich gesagt habe weder ich, noch meine Mitbewohnerin die Bereits im Master Mathematik ist, noch meine Studienkollegen in der Mathematik was von Abschlusseigenschaften gehört oder wüssten auf anhieb was damit gemeint ist. Gibt es da ein einfaches Beispiel für was man schnell versteht?! |
||||||
| 07.03.2012, 12:39 | Auf diesen Beitrag antworten » | ||||||
| Karlito | Ich kenne Abgeschlosseneit aus der Mathematik vorwiegend aus den Untervektorräumen. Damit wird ausgedrückt, dass man mit gewissen Operationen (Vektoraddition, Skalarprodukt) den Untervektorraum nicht verlässt. Genauso ist es hier. Abgeschlossen sind Sprachtypen nach bestimmten Operationen gdw. die Operation nicht dazu führt dann man in eine schwierigere Klasse kommt. Du weist ja sicher, dass jede Sprache eine Typ 0 Sprache ist, usw... Du wirst also mit den Operationen Vereinigung, Konkatenation und Kleene-Abschluss über einer Typ 2 Sprache immer wieder in einer Typ 2 Sprache landen. Für den Durchschnitt ist das nicht gegeben! Beispiel: D.h. Sprachen vom Typ 2 sind nicht unter Durchschnitt abgeschlossen. |
||||||
| Anzeige | |||||||
|
|
|||||||
| 10.03.2012, 16:16 | Auf diesen Beitrag antworten » | ||||||
| earthhero | Durchschnitt bedeutet ja, dass nur das übernommen wird, was bei beiden Sprachen vorkommt, also bei deinem Beispiel das a^n und b^n, Aber das wäre doch Typ 2, deine Beispiele mit a^n b^n c^m wäre das nicht Typ 1? |
||||||
| 10.03.2012, 16:18 | Auf diesen Beitrag antworten » | ||||||
| earthhero | Das würde ich von dem Bild so ablesen http://web318.server168.star-server.info...images/aufs.gif |
||||||
| 10.03.2012, 21:46 | Auf diesen Beitrag antworten » | ||||||
| Karlito | Hallo, a^nb^nc^m ist typ 2, da n gezählt werden muss (Aufbau des Stacks bei a, Abbau bei b) und der c Teil muss einach nur akzeptiert werden. Da Kellerautomat angebbar -> Typ 2. Durchschnitt übernimmt keine Wortteile sondern ganze Worte. Schließlich sind in den Mengen ganze Worte enthalten. Bei der einen Sprache sind a und b gleich oft, bei der anderen Sprache sind b und c gleich oft. Dadurch muss im Durchschnitt a, b und c gleich oft vorkommen... VG, Karlito |
||||||
|
|
