patternModerate
Are all context-free and regular languages efficiently decidable?
Viewed 0 times
efficientlyfreearealllanguagesregulardecidablecontextand
Problem
I came across this figure which shows that context-free and regular languages are (proper) subsets of efficient problems (supposedly $\mathrm{P}$). I perfectly understand that efficient problems are a subset of all decidable problems because we can solve them but it could take a very long time.
Why are all context-free and regular languages efficiently decidable? Does it mean solving them will not take a long time (I mean we know it without more context)?
Why are all context-free and regular languages efficiently decidable? Does it mean solving them will not take a long time (I mean we know it without more context)?
Solution
Regular language membership can be decided in $\cal{O}(n)$ time by simulating the language's (minimal) DFA (which has been precomputed).
Context free language membership can be decided in $\cal{O}(n^3)$ by the CYK Algorithm.
There are decidable languages that are not in $\sf{P}$, such as those in $\sf{EXPTIME}\setminus \sf{P}$.
Context free language membership can be decided in $\cal{O}(n^3)$ by the CYK Algorithm.
There are decidable languages that are not in $\sf{P}$, such as those in $\sf{EXPTIME}\setminus \sf{P}$.
Context
StackExchange Computer Science Q#315, answer score: 17
Revisions (0)
No revisions yet.