seka
Grünschnabel
Dabei seit: 24.01.2016
Beiträge: 2
|
|
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
. Mir fehlt der Ansatz :/ Wäre echt nice mir da auf die Sprünge zu helfen.
Danke im voraus.
LG
|
|
25.01.2016 00:13 |
|
|
|
seka
Grünschnabel
Dabei seit: 24.01.2016
Beiträge: 2
|
|
Genau da fängt es mit der planlosigkeit an
|
|
25.01.2016 09:42 |
|
|
|
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.
__________________ Syntax Highlighting fürs Board (Link)
|
|
25.01.2016 12:38 |
|
|
|
|
|