 Abschlusseigenschaften / Grammatiken |
earthhero
Jungspund
Dabei seit: 22.02.2012
Beiträge: 15
 |
|
| 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
|
|
05.03.2012 16:20 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
| RE: Abschlusseigenschaften / Grammatiken |
|
| Zitat: |
Original von earthhero
Wofür sind die Abschlusseigenschaften gut? Was bewirken die? Und was muss ich auf die Fragen "Was sind Abschlusseigenschaften" antworten?!
|
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
| Zitat: |
Original von earthhero
Einfach nur, dass auf der linken Seite max/min 1 Nichterminale stehen darf und die rechte Seite relativ egal ist?!
|
Ja!
| Zitat: |
Original von earthhero
"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.
|
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 09:36 |
|
|
earthhero
Jungspund
Dabei seit: 22.02.2012
Beiträge: 15
|
|
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?!
|
|
|
06.03.2012 22:04 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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:
![[latex]<br />
a^nb^nc^m \text{ist Typ 2}<br />
a^nb^mc^m \text{ist Typ 2}<br />
<br />
a^nb^nc^m \cap a^nb^mc^m = a^lb^lc^l \in \text{Typ 1}<br />
[/latex]](http://www.matheboard.de/latex2png/latex2png.php?<br />
a^nb^nc^m \text{ist Typ 2}<br />
a^nb^mc^m \text{ist Typ 2}<br />
<br />
a^nb^nc^m \cap a^nb^mc^m = a^lb^lc^l \in \text{Typ 1}<br />
)
D.h. Sprachen vom Typ 2 sind nicht unter Durchschnitt abgeschlossen.
|
|
|
07.03.2012 12:39 |
|
|
earthhero
Jungspund
Dabei seit: 22.02.2012
Beiträge: 15
|
|
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:16 |
|
|
earthhero
Jungspund
Dabei seit: 22.02.2012
Beiträge: 15
|
|
|
|
10.03.2012 16:18 |
|
|
|
