[Solved]: Can we prove that all CFLs can be recognized by a Turing Machine in polynomial time?

ignougroup
Problem Detail: 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.

Asked By : Kristen Hammack

Answered By : Raphael

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?
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33037