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!
$\begingroup$
$\endgroup$
$\begingroup$
$\endgroup$
Hint: Every context-free language is accepted by a pushdown automaton.
answered Dec 30 '15 at 20:32
-
$\begingroup$ Ok, we know that NTime[t(n)] = {L | ∃ nondeterministic TM M : L = L(M) and Tm ∈ O(t(n))} and we also know that every pushdown automaton with two stacks is equivalent in power to a Turing machine. So thats it? Or am I missing something? $\endgroup$ – toucheqt Dec 30 '15 at 20:58
-
$\begingroup$ There's only one way to tell. Imagine you were grading the assignment, and faced with this answer. Would you give yourself full grades? $\endgroup$ – Yuval Filmus Dec 30 '15 at 20:59
-
$\begingroup$ .. is accepted by a "real-time" pushdown automaton. $\endgroup$ – Hendrik Jan Dec 30 '15 at 21:59
$\begingroup$
$\endgroup$
It is actually in P, the CYK algorithm deterministically parses any string of length $n$ in time $O(n^3)$
-
2$\begingroup$ And P is a subset of NTIME(n)? That sounds wrong. $\endgroup$ – Raphael♦ Dec 30 '15 at 20:05
