| Die letzten 4 Beiträge |
| 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. |
| seka |
Genau da fängt es mit der planlosigkeit an 
|
| eulerscheZahl |
Gib einfach einen Algorithmus mit polynomieller Laufzeit an und begründe kurz die Korrektheit. |
| 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
. Mir fehlt der Ansatz :/ Wäre echt nice mir da auf die Sprünge zu helfen.
Danke im voraus.
LG |
|
|
