Aufgabe aus Klausur, Nacharbeitung |
| 09.10.2012, 13:50 | Auf diesen Beitrag antworten » | ||
| fromHTWDD | Aufgabe aus Klausur, Nacharbeitung Hey, ich habe eine Frage bezüglich einer Aufgabe meiner leider verhauenen TInf Klausur. Sie lautet: Jede kontextfreie Sprache, die nicht regulär ist, enthält unendlich viele reguläre Sprachen. Wie kann ich dies Beweisen ? Die Chomsky Hierachie sollte ja klar sagen, das die kontextfreie Sprache Typ2 und somit alle Typ3 Sprachen enthält. Stimmt das soweit? |
||
|
|
|||
| 09.10.2012, 19:04 | Auf diesen Beitrag antworten » | ||
| Karlito | Hi, ja, die Chomsky-Hierarchie besagt, dass Die Frage die sich stellt ist: Warum ist es bei einer Typ2 Sprache, die nicht Typ3 ist, immer notwendig, unendlich viele Sprachen vom Typ3 zu vereinigen, um die Typ2-Sprache zu erzeugen. Wenn mir dazu was einfällt sage ich bescheid. VG, Karlito |
||
| 09.10.2012, 19:23 | Auf diesen Beitrag antworten » | ||
| fromHTWDD | Danke für deine Antwort, Ich soll die Aussage betrachten, wenn sie falsch ist entsprechend Beweisen. Wenn sie richtig ist, entsprechend Beweisen. Nur ist mir einfach unklar, wie ich dies tun könnte. Leider gibt es keine offiziellen Lösungen :-( Und im Internet finde ich irgendwie auch nix dazu. Es war die erste Aufgabe aus dem 2. Semester Modul Theoretische Informatik. VG, Erik |
||
| 09.10.2012, 19:51 | Auf diesen Beitrag antworten » | ||
| Karlito | Hi, bei mir ist gerade der Groschen gefallen: Eine kontextfreie Sprache, welche nicht regulär ist, kann nicht durch einen endlichen Automaten (NFA/DFA) dargestellt werden. Jedes Wort einer kontextfreien Sprache kann durch einen endlichen Automaten dargestellt werden. Also ist die Sprache prinzipiell als Vereinigung einer Menge von Typ3-Sprachen darstellbar. Weiterhin sind alle regulären Sprachen unter der Vereinigung abgeschlossen. Könnte man nun die Typ2-Sprache, welche nicht Typ3 ist, mit einer endlichen Menge von Typ3-Sprachen bilden, so wäre Sie Typ3. <- Widerspruch. Einleuchtend? VG, Karlito |
||
| Anzeige | |||
|
|
|||
| 10.10.2012, 10:33 | Auf diesen Beitrag antworten » | ||
| fromHTWDD | Ich kann deiner Argumentation folgen, drauf gekommen wäre ich allerdings nicht. Wie eignet man sich dieses Verständnis an ? |
||
| 10.10.2012, 11:16 | Auf diesen Beitrag antworten » | ||
| Karlito | Hi, zuerst: ich glaube ich wäre in der Klausur vlt. auch nicht darauf gekommen. Was mir persönlich hilft ist: - mit andere darüber reden. Am besten einmal in der Woche mit einer Gruppe Leuten Zeit nehmen und einen Seminarraum nehmen und die Übungen mit Kommilitonen besprechen (Tafel ist wichtig, finde ich). Auch wenn du vlt nicht so gut mit Kommilitonen klar kommst: die Sichtweisen von anderen erweitern deinen eigenen Blick auf die Dinge. Ich versuche immer Anderen etwas zu erklären, das festigt und wenn man merkt, dass man es nicht erklären kann, hat man noch Verständnisdefizite.... - Immer als erstes alles aufschreiben was du weißt. Auch wenn es dir noch so trivial erscheint. D.h. bei unserem Beispiel: * Was sind die Eigenschaften von regulären Sprachen * Was sind die Eigenschaften von kontextfreien Sprachen * Wo liegen die Unterschiede * Konkret für das Beispiel: wie lassen sich kontextfreie Sprachen aus regulären Sprachen darstellen Sollte es bei euch nicht die Möglichkeit geben euch irgendwo zu treffen: - Frag die Dozenten/Übungsleiter was und kommuniziere, dass du gern wissen willst wie man auf die Lösung kommt. Oftmals sind die auch bereit per E-Mail zu antworten oder in einem persönlichen Gespräch. Dabei immer einen eigenen Ansatz und eigene Gedanken darlegen. Und ansonsten: - nil desperare (Niemals Aufgeben!) Auch bin ich auch gerne bereit weiter zu helfen (oder jemand anderes auf diesem Board). Ich versuche eigentlich immer, den Leuten zu helfen selbst auf die Lösung zu kommen (siehe Boardprinzip). Leider habe ich das bei diesem Beitrag nicht gemacht, da ich nicht wusste wie ich dich in die richtige Richtung stoße. Wenn du wieder hier anfragst, werde ich es versuchen dir die richtigen Hinweise zu geben. VG, Karlito |
||
| 18.11.2012, 15:25 | Auf diesen Beitrag antworten » | ||
| chrisp | Hallo, ich studiere ebenfalls an der HTW Informatik und beim Aufarbeiten dieser alten Klausurfrage haben wir diesen Beitrag gefunden. Allerdings ist uns die Antwort noch nicht ganz klar.
Also nochmal zum Verständnis: kontextfreie (Typ 2) Sprache wäre zb {a^n b^n für n Element N} reguläre (Typ 3) Sprache wäre zb. {a^n für n Element N} oder {b^n für n Element N} die Typ 2 Sprache, die nicht Typ 3 ist, kann doch mit einer Endlichen Menge Typ 3 Sprachen (nämlich den beiden unten genannten) gebildet werden ohne Typ 3 zu sein. Ich sehe da noch keinen Widerspruch. Kannst du vielleicht nochmal erläutern, warum die aus einer endlichen Menge von Typ3-Sprachen gebildete Sprache nach deiner Argumentation auch Typ 3 sein muss? |
||
| 18.11.2012, 16:10 | Auf diesen Beitrag antworten » | ||
| Karlito | Hallo, es gibt keine Operation, welche aus den Sprachen {a^n für n Element N} oder {b^n für n Element N} die Sprache a^nb^n erzeugt. Die vereinigung ist {a^n oder b^n}, der Schnitt ist leer und die Konkatenation erzeugt a^n b^m. Das mit den Typ3-Sprachen hängt mit den Abschlusseigenschaften von Typ3-Sprachen zusammen. Sie sind unter Vereinigung abgeschlossen, d.h. die Vereinigung von Typ3-Sprachen ist wieder eine Typ3-Sprache. Dies kann man leicht konstruieren, indem man für die Sprachen den DEA nimmt und einen neuen Startzustand einführt, welcher epsilon-übergänge zu den gewünschten Sprachen hat. Wie sicher bekannt ist, kann man zu jedem epsilon-NEA wieder einen äquivalenten DEA erstellen und somit ist die Vereinigung wieder Typ3. VG, Karlito |
||
| 10.07.2013, 19:51 | Auf diesen Beitrag antworten » | ||
| htwnpvoll | sehr nice erklärt. Und die allgeine Arbeitsidee für die Lösungsansätze hat bei mir jetz auch ein paar mal was gebracht. Danke |
||
| 11.07.2013, 11:53 | Auf diesen Beitrag antworten » | ||
| Karlito | Freut mich auch nach so langer Zeit noch positive Rückmeldungen zu bekommen. 
Gruß, Karlito |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
