 kontextfreie Sprachen - Abgeschlossenheit unter Komplement |
Knoedl
Grünschnabel
Dabei seit: 23.06.2007
Beiträge: 2
 |
|
| 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
|
|
23.06.2007 03:12 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
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.
|
|
|
23.06.2007 14:33 |
|
|
Knoedl
Grünschnabel
Dabei seit: 23.06.2007
Beiträge: 2
|
|
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
|
|
|
24.06.2007 15:35 |
|
|
|
