 Entscheidbarkeit regulärer Sprachen |
deppensido
Doppel-As
Dabei seit: 23.12.2012
Beiträge: 144
 |
|
| Entscheidbarkeit regulärer Sprachen |
     |
Hallo,
sind reguläre Sprachen entscheidbar? Meine Vermutung: Sie sind entscheidbar, da jede reguläre Sprache kontextfrei ist und es für kontextfreie Sprachen den CYK-Algorithmus gibt, der diese Sprachen entscheidet. Damit wären kontextfreie Sprachen also auch entscheidbar.
Liege ich mit der Vermutung richtig?
Grüße
|
|
21.03.2013 22:05 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Hallöchen,
theoretisch kann man das so begründen. Ich denke aber, du musst das wesentlich ausführlicher verargumentieren (evtl mit Beweis).
1. Die Menge der regulären Sprachen ist eine echte Teilmenge der kontextfreien Sprachen
2. Für jede kontextfreie Sprache L gibt es eine kontextfreie Grammatik, welche die Sprache L erzeugt
3. Das Wortproblem ![[latex]x \in L[/latex]](http://www.matheboard.de/latex2png/latex2png.php?x \in L) mit ![[latex]L[/latex]](http://www.matheboard.de/latex2png/latex2png.php?L) ist kontextfrei ist mittels der Grammatik, welche erzeugt entscheidbar (CYK-Algorithmus).
Das Wortproblem für reguläre Sprachen ist jedoch auch entscheidbar, ohne über kontextfreie Sprachen gehen zu müssen, da es für jede reguläre Sprache einen endlichen Automaten (NEA/DEA) gibt, welcher die Sprache entscheided. Ob ein Wort akzeptiert wird kann effektiv mittels dieses Automanten geprüft werden (muss evtl auch bewiesen werden).
VG,
Karlito
|
|
|
21.03.2013 22:54 |
|
|
deppensido
Doppel-As
Dabei seit: 23.12.2012
Beiträge: 144
|
|
hallo,
danke für die Erläuterung. Bei dieser Art von Aufgaben ist ein Beweis nicht notwendig, die Begründung sollte aber, wie du schon angemerkt hast, nachvollziehbar sein. Dass reguläre Sprachen entscheidbar sind, war jetzt auch nicht so offensichtlich, da wir im Skript lediglich den Satz hatten, dass reguläre Sprachen rekursiv aufzählbar sind. Könnte man alternativ auch begründen: reguläre Sprachen sind entscheidbar, da diese eine Teilmenge der Kontextfreien Sprachen ist und kontextfreie Sprachen eine Teilmenge der kontextsensitiven Sprachen, womit reguläre Sprachen auch kontextsensitiv sind? Da im Skript gezeigt wurde, dass kontextsensitive Sprachen entscheidbar sind, sind reguläre und auch kontextfreie Sprachen entscheidbar. Ist jetzt keine Übungsaufgabe, könnte aber vielleicht in meiner Klausur dran kommen.
Grüße
|
|
|
21.03.2013 23:32 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Hallo,
ja natürlich kannst du diese Beziehung auch nutzen. Es ist doch völlig egal welche Obermenge Du benutzt... Wäre das Wortproblem für Typ-0 Sprachen entscheidbar, könntest Du auch das nehmen. Immer vorrausgesetzt Du darfst auf die Teilmengenbeziehung ohne Beweis zurückgreifen.
Außerdem: Schau mal genau im Skript nach. Ich habe selbst ein wenig googlen müssen. Rekursive Sprachen sind entscheidbar. Rekursiv aufzählbare Sprachen sind semientscheidbar. Schau da noch einmal genau nach.
VG,
Karlito
|
|
|
22.03.2013 00:01 |
|
|
deppensido
Doppel-As
Dabei seit: 23.12.2012
Beiträge: 144
|
|
ähm, heißt das jetzt, dass reguläre und kontextfreie Sprachen "nur" rekursiv aufzählbar sind? Da der CYK-Algorithmus evtl. in eine Endlosschleife gehen könnte, bei einem Wort das nicht in der Sprache ist? Aber würde mir komisch vorkommen, da der CYK-Alg. ja das Wortproblem entscheidet.
Grüße
|
|
|
22.03.2013 00:21 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Hi,
nein, ich denke, die Sprachen müssten rekursiv sein. Ich denke das sollte so im Skript stehen. Deswegen sagte ich, Du solltest mal schauen, wie es im Skript formuliert ist. Vlt kannst du die Entscheidbarkeit schon dadurch ableiten.
VG,
Karlito
|
|
|
22.03.2013 00:27 |
|
|
deppensido
Doppel-As
Dabei seit: 23.12.2012
Beiträge: 144
|
|
hallo,
nur Anhand der Definition von Rekursiven Sprachen kann man die Entscheidbarkeit regulärer Sprachen nicht herleiten, da noch zusätzlich begründet werden muss, dass eine Turingmaschine , die eine reguläre Sprache entscheidet, auch immer hält, denke ich.
Grüße
|
|
|
22.03.2013 00:55 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Naja, laut wiki ist eine rekursive Sprache entscheidbar. Ich erinnere mich dunkel, dass man die Rekursion so gestalten kann, dass nachweisbar ist, dass das gesuchte Wort nicht mehr in der Sprache sein kann. Und das in endlicher Zeit -> Entscheidbar. Bin da aber leider momentan auch nicht mehr so in dem Thema drin.
Wenn ich dazu komme, schlage ich das morgen mal nach.
VG,
Karlito
|
|
|
22.03.2013 01:06 |
|
|
|
