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
|
|