|
  |
 Aufgabe aus Klausur, Nacharbeitung |
fromHTWDD
Grünschnabel
Dabei seit: 09.10.2012
Beiträge: 3
 |
|
| 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 13:50 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Hi,
ja, die Chomsky-Hierarchie besagt, dass ![[latex]Typ3 \subset Typ2[/latex]](http://www.matheboard.de/latex2png/latex2png.php?Typ3 \subset Typ2) . Ich weis jedoch nicht ob dir das weiter hilft, da du ja Sprachen betrachten sollst, die vom Typ2 und nicht vom Typ3 sind und ![[latex]Typ2 \backslash Typ3 \neq \emptyset[/latex]](http://www.matheboard.de/latex2png/latex2png.php?Typ2 \backslash Typ3 \neq \emptyset)
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:04 |
|
|
fromHTWDD
Grünschnabel
Dabei seit: 09.10.2012
Beiträge: 3
|
|
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:23 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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
|
|
|
09.10.2012 19:51 |
|
|
fromHTWDD
Grünschnabel
Dabei seit: 09.10.2012
Beiträge: 3
|
|
Ich kann deiner Argumentation folgen, drauf gekommen wäre ich allerdings nicht.
Wie eignet man sich dieses Verständnis an ?
|
|
|
10.10.2012 10:33 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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
|
|
|
10.10.2012 11:16 |
|
|
chrisp
Grünschnabel
Dabei seit: 18.11.2012
Beiträge: 1
|
|
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.
| Zitat: |
| 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. |
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 15:25 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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
|
|
|
18.11.2012 16:10 |
|
|
htwnpvoll
unregistriert
|
|
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
|
|
|
10.07.2013 19:51 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Freut mich auch nach so langer Zeit noch positive Rückmeldungen zu bekommen. 
Gruß,
Karlito
|
|
|
11.07.2013 11:53 |
|
|
|
|
|
|
|
|
