the Chomsky hierarchy vs. classical complexity classes

Question

What are the obvious (and less obvious) relationships between classical complexity classes like P,NP,PSPACE,EXP and the Chomsky hierarchy of grammars for the language $L$ in question, context-free and context-sensitive ? I have only one: regular is a strict subset of P.

Answer 1

There are several relationships:

1. $\textsf{REG} = \textsf{DSPACE}(O(1)) = \textsf{NSPACE}(O(1))$. There are a couple steps in this proof:

• We may view DFAs as Turing Machines (TMs) that use $O(1)$ space. This gives us $\textsf{REG} \subseteq \textsf{DSPACE}(O(1))$. For the reverse inclusion, we effectively view the configuration graphs of TMs that use $O(1)$ space as DFAs.
• Change DFA to NFA, and we obtain that $\textsf{REG} = \textsf{NSPACE}(O(1))$
• Note that by Kleene's Theorem, DFAs and NFAs are equally powerful.

2. I am not entirely sure as to the best upper bound for $\textsf{CFL}$. However, $\textsf{LOGCFL}$ is the class of decision problems that are logspace reducible to CFLs. Clearly, $\textsf{CFL} \subseteq \textsf{LOGCFL}$. It is known that $\textsf{LOGCFL} = \textsf{SAC}^{1} \subseteq \textsf{AC}^{1}$.

3. $\textsf{CSL} = \textsf{NSPACE}(O(n))$. [Kur64]

[Kur64] S. Y. Kuroda. Classes of languages and linear-bounded automata, Information and Control 7:207-233, 1964.