Tous les langages sans contexte et réguliers sont-ils décidables de manière efficace?

Je suis tombé sur cette figure qui montre que les langages sans contexte et réguliers sont des sous-ensembles (appropriés) de problèmes efficaces (supposément ). Je comprends parfaitement que les problèmes efficaces sont un sous-ensemble de tous les problèmes décidables car nous pouvons les résoudre, mais cela peut prendre très longtemps.$\mathrm{P}$

Pourquoi tous les langages sans contexte et réguliers sont-ils décidables efficacement? Est-ce que cela signifie que les résoudre ne prendra pas longtemps (je veux dire que nous le savons sans plus de contexte)?

$\cal{O}(n)$

$\cal{O}(n^3)$

$\sf{P}$$\sf{EXPTIME}\setminus \sf{P}$

Affinement / "petits caractères" sur réponse de DC: tous les CFL sous forme de Chomsky Normal Form peuvent être analysés efficacement avec l'algorithme CYK et tous les CFL peuvent être convertis en CNF. Cependant, la conversion d' un CFL arbitraire en CNF peut prendre de l'espace exponentiel dans le pire des cas en fonction de certains algorithmes. (Je ne connais pas d'algorithme garantissant la conversion du temps P ici, est-ce quelqu'un d'autre? Il faut considérer tous les cas extrêmes / pires tels que les LFC non déterministes ou ambiguës .) Wikipédia déclare dans la section CNF Ordre des transformations

$|G|^2$$2^{2 |G|}$

Il semble donc qu'il puisse exister des LFC qui ne sont pas efficacement analysables. La plupart des langages de programmation sont efficacement convertibles en CNF (ou peut-être principalement définis en CNF ou presque CNF), donc l'analyse syntaxique CFL pour les langages "typiques" est "pratiquement" en P. trouver des articles récents sur la recherche rapide). Par exemple, ce document de recherche plus ancien (1973) de Greibach semble également indiquer que les performances dans le pire des cas peuvent ne pas être limitées par P. voir par exemple.

• La langue sans contexte la plus difficile / Greibach