This question came up while a group of students at my school were studying for our qualifying exams. The question on an old exam was,

Consider the following six classes of languages: Context free (CFL), Regular(REG), P, NP, Recursive(R), and Recursively enumerable(RE). (1) indicate the relationships between these six classes e.g., by drawing a Venn diagram. (2) name the minimum type of machine needed to recognize languages in the different classes.

OK, so we know that REG$\subseteq$CFL, either P$\subseteq$NP or P=NP, NP=RE, and P=R.

We also know that the minimum machine type for each language class is REG:DFA, CFL:PDA, P/R:DTM, NP/RE:might be NTM.

We know that a Turing machine is more powerful than a pushdown automata, but we can't find anything that actually proves that all CFLs can be recognized in polynomial time, or think of a way to prove it ourselves. When I asked the teacher who originally wrote the problem about this, he didn't have a ready answer.

  • 1
    $\begingroup$ What's the question? "Thoughts?" isn't a question. Please make sure the body of your question contains the question that you want an answer to. Also, tell us what research you've done, where you've looked. Do you know how to build a parser/recognizer for an arbitrary CFL? $\endgroup$
    – D.W.
    Nov 12 '14 at 22:16

Why, of course. I'd expect any formal language textbook to contain at least proof of this statement:

The CYK algorithm¹ parses context-free grammars in polynomial time.

Furthermore, note that every CFL is accepted by a PDA (in linear time). PDAs can be simulated by TMs with polynomial overhead.²

  1. Or any other suitable parsing algorithm; there are several.
  2. This claim is somewhat true (we always have the other proof after all) but I don't actually know a direct simulation. Do you?
  • $\begingroup$ Any idea what is the complexity of CYK when implemented on a Turing machine? (just wondering, not a critique) $\endgroup$ Nov 13 '14 at 0:06
  • $\begingroup$ @HendrikJan Good question. It's $\Theta(n^3)$ in RAM-style models, of course. Is an additional linear factor enough for moving on the tape enough if we hard-code the grammar in states? (There's surely more overhead if we try to keep the TM algorithm parametric in the grammar.) $\endgroup$
    – Raphael
    Nov 13 '14 at 6:58
  • 1
    $\begingroup$ On the second point: the CYK algorithm is essentially matrix multiplication, so it has the same time complexity. $\endgroup$ Nov 13 '14 at 10:17
  • $\begingroup$ I posted a follow-up question regarding that overly optimistic statement of mine here. Thanks, @A.Schulz! $\endgroup$
    – Raphael
    Nov 13 '14 at 11:03

There are several misconceptions in this question and too many to cover in a comment.

  1. We do not know that $\mathrm{P}=\mathrm{R}$ or that $\mathrm{NP}=\mathrm{RE}$. In fact, we know that both of these things are false. The time hierarchy theoreom tells us that both $\mathrm{P}$ and $\mathrm{NP}$ are strictly contained within the recursive languages.

  2. $\mathrm{P}$ is not the class of languages accepted by any old deterministic Turing machines: they're DTMs running in polynomial time. Similarly, $\mathrm{NP}$ languages are accepted by NTMs running in polynomial time.

  3. Without time bounds, the class of deterministic TMs and the class of nondeterministic TMs accept exactly the same languages: you can simulate nondeterminism deterministically but exponentially slower.

  4. Also, we know that $\mathrm{REG}\subsetneq\mathrm{CFL}$, which is consistent with what you wrote but a stronger statement. Exercise: can you give an example of a context-free language that is not regular?

  5. Another nitpick: you write "$\mathrm{P}\subseteq\mathrm{NP}$ or $\mathrm{P}=\mathrm{NP}$"; the second statement is already included in the first.


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.