Informatiker Board | Berechenbarkeits- und Komplexitätstheorie

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » Zeige, dass xxx in P liegen

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Zeige, dass xxx in P liegen

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

seka
Grünschnabel

Dabei seit: 24.01.2016
Beiträge: 2

Zeige, dass xxx in P liegen

Zitatantwort auf diesen Beitrag erstellen

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

25.01.2016 00:13

Nehmen Sie seka in Ihre Freundesliste auf

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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

__________________
Syntax Highlighting fürs Board (Link)

25.01.2016 06:02

Nehmen Sie eulerscheZahl in Ihre Freundesliste auf

seka
Grünschnabel

Dabei seit: 24.01.2016
Beiträge: 2

Genau da fängt es mit der planlosigkeit an verwirrt

25.01.2016 09:42

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » Zeige, dass xxx in P liegen