Entscheidbarkeit regulärer Sprachen

Neue Frage »

Auf diesen Beitrag antworten »
deppensido 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
 
Auf diesen Beitrag antworten »
Karlito

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] mit [latex]L[/latex] ist kontextfrei ist mittels der Grammatik, welche [latex]L[/latex] 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
Auf diesen Beitrag antworten »
deppensido

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
Auf diesen Beitrag antworten »
Karlito

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
 
Auf diesen Beitrag antworten »
deppensido

ä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
Auf diesen Beitrag antworten »
Karlito

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
Auf diesen Beitrag antworten »
deppensido

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
Auf diesen Beitrag antworten »
Karlito

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
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »