Klassifikation von Sprachen < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 15:16 Do 22.09.2011 | | Autor: | Harris |
| Aufgabe | Gegeben seien die folgenden Klassen von Sprachen:
- die kontextfreien Sprachen CFL
- NP
- die rekursiv aufzählbaren (oder positiv semi-entscheidbaren) Sprachen RE
- die regulären Mengen REG
- E die rekursiven oder entscheidbaren Sprachen REK
Ordnen Sie diese Klassen bezüglich der bekannten und bewiesenen Inklusionen und begründen Sie Ihre Antwort in der Form: "Die Klasse X wird durch Maschinen des Typs x definiert und diese sind ein Spezialfall von Maschinen des Typs y für Y.
Wo gelten echte Inklusionen und warum? |
Hi!
Diese schöne Aufgabe haben wir gerade vor uns liegen und wir sind uns nicht ganz einig.
Aber erstmal das, was wir haben:
- REG: Definiert durch endlichen Automaten
- CFL: Definiert durch Kellerautomaten (Erweiterung des endlichen Automatens)
- NP: Definiert durch alle Entscheidungsprobleme, die durch eine nichtdeterministische Turingmaschine in polynomieller Zeit entscheidbar sind. (Eine Turingmaschine ist nichts anderes als ein Kellerautomat mit 3 Kellern)
- REK: Alle Probleme, die durch eine Turingmaschine entscheidbar sind (Eine nichtdeterministische TM lässt sich durch eine deterministische simulieren. Einzige Einschränkung bei NP ist die Zeit)
- RE: Alle Probleme, die durch eine Turingmaschine semi-entscheidbar sind (Aus entscheidbar folgt Semi-entscheidbar)
Überall echte Inklusionen, da:
[mm] \{a^nb^n\}\not\in [/mm] REG aber [mm] \in [/mm] CFL
[mm] \{a^nb^nc^n\} \not\in [/mm] DFL aber [mm] \in [/mm] NP
Und jetzt kommts:
Das Problem: "Eingabe eine natürliche Zahl. Sind nach dieser Zahl die nächsten [mm] $n^n$ [/mm] Zeichen mit Blanks gefüllt (= leer)?"
ist meiner Meinung entscheidbar (da nur [mm] $n^n$ [/mm] Schritte gebraucht werden) aber nicht nichtdeterministisch in Polynomialzeit lösbar. Stimmt das?
Das Problem: "Ist das Band einer Turingmaschine nicht komplett leer?" ist ein positiv semi-entscheidbares Problem, denn wenn es nicht leer ist, terminiert das Programm nach endlicher Zeit. Wenn es leer ist, terminiert es nicht."
Stimmt die Antwort auf die Frage so?
Gruß, Harris
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:20 Sa 24.09.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
