Ich bin auf diese Abbildung gestoßen, die zeigt, dass kontextfreie und reguläre Sprachen (richtige) Teilmengen effizienter Probleme sind (angeblich ). Ich verstehe vollkommen, dass effiziente Probleme eine Teilmenge aller entscheidbaren Probleme sind, weil wir sie lösen können, aber es kann sehr lange dauern.
Warum können alle kontextfreien und regulären Sprachen effizient entschieden werden? Bedeutet das, dass es nicht lange dauern wird, sie zu lösen (ich meine, wir wissen es ohne weiteren Kontext)?
Antworten:
Die reguläre Zugehörigkeit zu einer Sprache kann in werden, indem der (vorberechnete) (minimale) DFA der Sprache simuliert wird.O ( n )
Die kontextfreie Sprachenmitgliedschaft kann in durch den CYK-Algorithmus festgelegt werden .O ( n3)
Es gibt entscheidbare Sprachen, die nicht in , z. B. die in .P E X P T I M E ∖ P
quelle
Verfeinerung / "Kleingedrucktes" bei Beantwortung durch DC: Alle CFLs in Form der Chomsky-Normalform können mit dem CYK-Algorithmus effizient analysiert und alle CFLs in CNF konvertiert werden. Das Konvertieren einer beliebigen CFL in CNF kann jedoch abhängig von einigen Algorithmen im schlimmsten Fall einen exponentiellen Raum beanspruchen. (Mir ist kein Algorithmus bekannt, der hier eine P-Zeit-Konvertierung garantiert, oder? Man muss alle Edge / Worst-Cases wie nicht deterministische oder mehrdeutige CFLs berücksichtigen .) Wikipedia-Angaben zum CNF-Abschnitt Reihenfolge der Transformationen
Daher scheint es möglicherweise CFLs zu geben, die nicht effizient analysiert werden können. Die meisten Programmiersprachen sind effizient konvertierbar zu CNF (oder vielleicht meist definiert in CNF oder nahezu CNF) daher CFL für „typische“ Sprachen Parsen ist „praktisch“ in P. Es gibt wohl einige moderne Forschung in diese schlimmen Fall Komplexität (aber nicht aktuelle Beiträge dazu finden Sie in der Cursorsuche). ZB scheint diese ältere (1973) Forschungsarbeit von Greibach auch darauf hinzudeuten, dass die Worst-Case-Leistung möglicherweise nicht durch P. beschränkt ist, siehe z.
quelle