| Die letzten 4 Beiträge |
| Tobias |
| Zitat: |
Original von Knoedl
vielen Dank fuer deine Antwort :-). Aber ich glaub, der letzte Satz ist falsch: [...]
|
Unter Einbezug deiner erweiterten Erkenntnisse kann man meine Aussage verfeinern, das ist richtig. Aber wenn man einfach nur die mathematische Negation als Argumentationsgrundlage nimmt, dann ist meine Aussage richtig. Außerdem habe ich den Fall, dass das Komplement einer Typ-2 Sprache auch Typ-2 ist nicht ausgeschlossen. |
| Knoedl |
Hallo Tobias,
vielen Dank fuer deine Antwort :-). Aber ich glaub, der letzte Satz ist falsch:
| Zitat: |
Original von Tobias
Das Komplement einer Typ-2 Sprache kann demnach Typ-1 oder Typ-0 sein. |
zunaechst mal kann das Komplement einer Typ-2 Sprach natuerlich auch vom Typ-2 sein.
Zum anderen sind Typ-2 Sprachen auch vom Typ-1. Und Typ-1-Sprachen sind unter dem Komplement abgeschlossen. Folglich kann das Komplement von Typ-2 Sprachen nur vom Typ-1 sein, nicht von Typ-0.
Danke nochmal 
mfg, Knoedl |
| Tobias |
Wenn wir ein endliches Alphabet ![[latex]\Sigma[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\Sigma) haben und eine Sprache ![[latex]L \subset \Sigma^\ast[/latex]](http://www.matheboard.de/latex2png/latex2png.php?L \subset \Sigma^\ast) betrachten, dann ist das Komplement definiert durch ![[latex]L^C = \Sigma^\ast \backslash L[/latex]](http://www.matheboard.de/latex2png/latex2png.php?L^C = \Sigma^\ast \backslash L) .
Und die Nichtabgeschlossenheit einer kontextfreien Sprache ![[latex]L[/latex]](http://www.matheboard.de/latex2png/latex2png.php?L) unter dem Komplement bedeutet nun nichts weiter, als dass die Sprache ![[latex]L^C[/latex]](http://www.matheboard.de/latex2png/latex2png.php?L^C) nicht kontextfrei sein muss.
Nehmen wir die von dir angesprochenen Chomsky Hierarchie:
Kontextfreie Sprachen sind Typ-2. Reguläre Sprachen (Typ-3) sind ebenfalls kontextfrei aber nicht andersrum. Salopp kann man es so ausdrücken:
![[latex]\textbf{Typ-3} \subset \textbf{Typ-2} \subset \textbf{Typ-1} \subset \textbf{Typ-0}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\textbf{Typ-3} \subset \textbf{Typ-2} \subset \textbf{Typ-1} \subset \textbf{Typ-0})
Das bedeutet, wenn eine Typ-x Sprache unter einer Operation nicht abgeschlossen ist, dann führt die Operation aus dem Typ-x heraus zu einem Typ-y mit y < x.
Das Komplement einer Typ-2 Sprache kann demnach Typ-1 oder Typ-0 sein. |
| Knoedl |
kontextfreie Sprachen - Abgeschlossenheit unter Komplement
Hallo zusammen!
kontextfreie Sprachen sind ja bekanntlich unter Komplement nicht abgeschlossen.
Ich bin mir da noch nicht ganz im klaren was das bedeutet. Bedeutet das jetzt nur, dass das Komplement einer Typ-2 Sprache unter Umstaenden vom Typ-1 ist, oder koennte sie sogar auch vom Typ-0 sein?
Irgendwie weiss ich noch ned so ganz wie sich das verhaelt mit der Nichtabgeschlossenheit einer Sprachklasse unter einer Operation. Ist die Sprache, auf die ein Operand angewendet wurde, der fuer diese Sprachklasse als nicht abgeschlossen gilt, dann hoechstens von der naechst niedrigeren Sprachklasse oder vielleicht von noch nierigeren. Oder gibt es da keinen Zusammenhang?
Vielen Dank schonmal fuer eure Hilfe!
mfg, Knoedl |
|
|
