1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

Hint: Every context-free language is accepted by a pushdown automaton.

$\endgroup$
  • $\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
0
$\begingroup$

It is actually in P, the CYK algorithm deterministically parses any string of length $n$ in time $O(n^3)$

$\endgroup$
  • 2
    $\begingroup$ And P is a subset of NTIME(n)? That sounds wrong. $\endgroup$ – Raphael Dec 30 '15 at 20:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.