Zeige, dass xxx in P liegen

Neue Frage »

Auf diesen Beitrag antworten »
seka Zeige, dass xxx in P liegen

Hallo Leute,
ich will es kurz machen, folgende Aufgabe liegt vor mir: Zeige, dass LP(DFA) (Leerheitsprobem für dfas), SP(DFA), IP(DFA) und ÄP(DFA) in P liegen, also effizient lösbar sind.
Ich weiß, dass P die Klasse ist, der man die Probleme, die sich mit einem deterministischen Algorithmus in polynomieller Laufzeit lösen lassen, zuordnet. Zum anderen ist mir bewusst, dass obige Probleme für Typ3-Grammatiken entscheidbar sind, die Beweise habe ich bereits. Mir ist ehrlich gesagt nicht ersichtlich wie ich den Beweis für die Entscheidbarkeit mit polynomieller Zeitbeschränkung zu zeigen habe verwirrt . Mir fehlt der Ansatz :/ Wäre echt nice mir da auf die Sprünge zu helfen.
Danke im voraus.
LG
 
Auf diesen Beitrag antworten »
eulerscheZahl

Gib einfach einen Algorithmus mit polynomieller Laufzeit an und begründe kurz die Korrektheit.
Auf diesen Beitrag antworten »
seka

Genau da fängt es mit der planlosigkeit an verwirrt
Auf diesen Beitrag antworten »
eulerscheZahl

Damit die Sprache nicht leer ist, musst du vom Startzustand aus in einen Endzustand kommen.
Das kannst du ganz einfach mit Breitensuche oder Tiefensuche testen, geht also in polynomieller Zeit.
Damit hast du dann auch schon einen Weg zum Endzustand und somit ein Wort der Sprache, wenn du die Terminalsymbole an den Kanten aufschreibst.
 
 
Neue Frage »
Antworten »


Verwandte Themen

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