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!
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
It is actually in P, the CYK algorithm deterministically parses any string of length $n$ in time $O(n^3)$