patternMinor
What is the big-O (worst-case upper bound) for time and space requirement of the different Chomsky classes?
Viewed 0 times
casetheboundspacewhatchomskytimerequirementdifferentbig
Problem
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!
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!
Solution
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.
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.
Context
StackExchange Computer Science Q#65915, answer score: 3
Revisions (0)
No revisions yet.