As the question states, how do we prove that for every L ∈ L2 (context-free class of languages) is true that L ∈ NTIME(n)?
Can anyone point me to a proof or outline it here? Thanks!
As the question states, how do we prove that for every L ∈ L2 (context-free class of languages) is true that L ∈ NTIME(n)?
Can anyone point me to a proof or outline it here? Thanks!
Hint: Every context-free language is accepted by a pushdown automaton.
It is actually in P, the CYK algorithm deterministically parses any string of length $n$ in time $O(n^3)$