Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
---- Berechenbarkeits- und Komplexitätstheorie (http://www.informatikerboard.de/board/board.php?boardid=15)
----- Zeige, dass xxx in P liegen (http://www.informatikerboard.de/board/thread.php?threadid=2814)

Geschrieben von seka am 25.01.2016 um 00:13:

  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


Geschrieben von eulerscheZahl am 25.01.2016 um 06:02:

 

Gib einfach einen Algorithmus mit polynomieller Laufzeit an und begründe kurz die Korrektheit.


Geschrieben von seka am 25.01.2016 um 09:42:

 

Genau da fängt es mit der planlosigkeit an verwirrt


Geschrieben von eulerscheZahl am 25.01.2016 um 12:38:

 

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.


Forensoftware: Burning Board, entwickelt von WoltLab GmbH