Mächtigkeit von Sprachen < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo,
ich beschäftige mich gerade mit den Abschlusseigenschaften von Formalen Sprachen. Die Typ-3- und Typ-1-Sprachen sind unter allen Punkten: Schnitt, Vereinigung, Komplement, Konkatenation und Stern abgeschlossen. Müssten das dann nicht theoretisch auch die "mächtigsten" Sprachen sein, da man damit viel mehr machen kann? Aber das Widerspricht irgendwie dem was ich in der Vorlesung gehört habe, nämlich das die Typ-0-Sprachen die mächtigsten sind....Könnte mir jemand das erklären?
Liebe Grüße :)
|
|
| |
|
Hallo judithlein,
> Hallo,
>
> ich beschäftige mich gerade mit den Abschlusseigenschaften
> von Formalen Sprachen. Die Typ-3- und Typ-1-Sprachen sind
> unter allen Punkten: Schnitt, Vereinigung, Komplement,
> Konkatenation und Stern abgeschlossen. Müssten das dann
> nicht theoretisch auch die "mächtigsten" Sprachen sein, da
> man damit viel mehr machen kann? Aber das Widerspricht
> irgendwie dem was ich in der Vorlesung gehört habe,
> nämlich das die Typ-0-Sprachen die mächtigsten
> sind....Könnte mir jemand das erklären?
Ich würde sagen, dass alles, was Typ 1,2,3-Sprachen machen, die Typ 0-Sprachen nicht "kratzt".
Es gilt doch die Beziehung [mm]\text{Typ 0}\supset\text{Typ 1}\supset\text{Typ 2}\supset\text{Typ 3}[/mm]
Wenn du also eine Sprache vom Typ 1,2 oder 3 hast, so ist diese doch insbesondere vom Typ 0 - nur mit weiteren Einschränkungen.
Mit Typ 0-Sprachen überdeckst du doch die anderen Typen ...
Ob also Typ 1,2,3-Sprachen irgendwie abgeschlossen sind, ist egal, es bleibt (insbesondere) Typ 0
>
> Liebe Grüße :)
Ich lasse das aber mal auf "teilweise beantwortet" - vllt. kann jemand das formaler ausdrücken oder falls ich daneben liege ...
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:13 Mi 01.02.2012 | | Autor: | judithlein |
Ja...ich verstehe. Manchmal frage ich mich wieso ich nicht ein paar Minuten länger selbst darüber nachgedacht habe...Danke!
|
|
|
| |
|
Hio!
Nur der Vollständigkeit halber (und damit evt. etwas formaler):
Für Typ-0 Sprachen gibt es eine Turingmaschine die diese entscheidet, jedoch kann das unter Umständen unendlich lange dauern! (Das ist gerade die Definition für Typ-0 Sprachen)
Das heißt in Typ-0 Sprachen sind alle Sprachen/Probleme, für die das Halteproblem gelöst oder eben auch nicht gelöst werden kann.
Da nach Church-Turing-These eine Turingmaschine alle intuitiv berechenbaren Funktionen umfasst, kann man mit einer Turingmaschine also im Prinzip "alles lösen".
Anders ausgedrückt:
Mit Hilfe einer Turingmaschine kann man insbesondere z.B.: auch Kellerautomaten oder (deterministische) endliche Automaten simulieren. Damit umfassen Typ-0 Sprachen mehr Probleme als die übrigen Sprachen und sind damit "größer"
Siehe hierzu auch nochmal Wiki: http://de.wikipedia.org/wiki/Typ-0-Sprache
|
|
|
| |
|
Ok, danke. Das verstehe ich. Aber das mit dem Halteproblem...das ist doch eben nicht entscheidbar...Deswegen verstehe ich gerade deine Anmerkung dazu nicht. Oder habe ich das falsch verstanden mit dem Halteproblem?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:20 Mo 06.02.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:15 Di 07.02.2012 | | Autor: | Pille456 |
Hio!
Ich hatte mich mit dem Halteproblem etwas unklar ausgedrückt bzw. ist der Satz einfach dumm formuliert sorry
Das hat nichts direkt mti dem Halteproblem zu tun
|
|
|
|
