4
$\begingroup$

Everybody knows the Chomsky-hierarchy for describing formal languages and big-O notation for describing time and space complexity of a function.

We know, that each class in the Chomsky-hierarchy corresponds to an atomata, that can recognize any language in the corresponding class.

The question is: What is the worst-case time and space complexity of these automatas given any language of the above class?

What I found out already:

Chomksy-3 class, the regular languages can be recognized by an FSM of n-states where n is a finite number. IMO this makes it require O(n) space and O(l) time, where l is the length of the input.

Chomsky-2 class, the context free languages can be recognised by a Non-deterministic pushdown automaton. CYK algorithm run $n^3 * G$ where n is the length of the input and G is the number of rules in the grammar in Chomsky Normal form.

But how much space needed? Do we have better bounds?

Chomsky-1 class, the context sensitive languages can be recognised by a Linear-bounded non-deterministic Turing machine.

This class seem to depend on the length of the context to be recognised. Maybe in exponential time.

Chomksy-0 class, the recursively enumerable languages can be recognised by Turing machine.

Can anything stated for this class? If not, why? Maybe the $P \stackrel{?}{=} NP$ problem is related.

Are the above statements true?

Please give citations to your answer!

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ This is too many questions in one post. Please break it up into at least one question per class. Even then, you're still asking about upper and lower bounds on time and space, which may be too broad if the answers are not trivial. $\endgroup$ – Raphael♦ Nov 12 '16 at 19:31
  • 1
    $\begingroup$ You may want to clarify if you are interested if you are interested in deciding each individual language, or in the four decision problems "Given $G \in X$ and $w \in \Sigma^*$, is $w \in L(G)$?". The answers differ. $\endgroup$ – Raphael♦ Nov 12 '16 at 19:36
  • 1
    $\begingroup$ Also, more information than you give is given even on Wikipedia. It says, for instance, that the universal word problem for CSL is PSPACE-complete, and that there are PSPACE-complete CSLs. What more do you need? $\endgroup$ – Raphael♦ Nov 12 '16 at 19:37
  • $\begingroup$ @Raphael: I'm not an expert on the topic. I mean to the worst-case scenario on "parsing" any language of the class. I thought there is some high asymptotic function (exponential or so), that makes using these classes practically impossible. On wikipedia there is a table of the classes and the corresponding automata, but no mention of the time and space requirement even for regular languages, which is easy. I agree there is a clue that CSLs are PSPACE, but it is hard to find and the rest is missing. $\endgroup$ – deadbeef Nov 13 '16 at 18:56
3
$\begingroup$

Regular languages can be accepted in linear time and constant space.

Valiant's algorithm parses arbitrary context-free languages in time $O(n^\omega)$, where $\omega$ is the matrix multiplication constant. Deterministic context-free languages (which are those used in practice) can be parsed in linear time.

Context-sensitive languages are identical to the class $\mathsf{NSPACE}(n)$. I'm not aware of any non-trivial time upper bound.

Recursively enumerable languages cannot be parsed in general, since $\mathsf{R} \neq \mathsf{RE}$.

The $\mathsf{P}\stackrel?=\mathsf{NP}$ question is completely unrelated. Unfortunately, the undergraduate curriculum usually spends much more time on the old-fashioned Chomsky hierarchy compared to more modern hierarchies afforded by computational complexity theory.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Regular languages are OK. I never heard of Valiant's algorithm (found nice citation on wikipedia: Lillian Lee (2002)) only Earley and CYK somehow. Do you know why? What about the space required by Valiant's algorithm? I accept your answer CS languages and RE languages. I recived a rather old and application centric curriculum, and also all books I have read on applying this topic did not contained other theoretical background. What you told me is completely new. Thank you. $\endgroup$ – deadbeef Nov 12 '16 at 14:04
  • $\begingroup$ Valiant's algorithm isn't practical, so that explains why you never heard of it. Its space usage is most likely $\Theta(n^\omega)$. $\endgroup$ – Yuval Filmus Nov 12 '16 at 14:07
  • $\begingroup$ What do you mean with "isn't practical" and "most likely"? Could you cite your statement? $\endgroup$ – deadbeef Nov 12 '16 at 14:13
  • $\begingroup$ You'll just have to trust me. Or you could ask a question about it. But basically, fast matrix multiplication algorithms aren't practical, and have similar time and space usages. $\endgroup$ – Yuval Filmus Nov 12 '16 at 14:14
  • $\begingroup$ "more modern hierarchies" -- arguably, Chomsky classes are much more relevant in many more contexts, so.... but let's not flame-war here. $\endgroup$ – Raphael♦ Nov 12 '16 at 19:33

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.