> I can't think of a single case where Chomsky type-0 or type-1 grammars are relevant to any practical concept in computer science.
Not the grammars per se, but the notion that there are things computer programs cannot do -- and that we have a good handle on what these things are -- is an important one.
As for Chomsky's Type 1, I've seen no evidence that the concept of a context-sensitive language has been of practical use to anyone, ever. It looks like an idea that turned out to be a dead end.
EDIT. To clarify: Certainly there are CSLs that have been of practical use. But the fact that a certain language is or is not a CSL, does not seem to be something worth knowing.
This is exactly what I'm talking about, but because people already have a basic understanding of context and so on, they don't appreciate the significance of Chomsky's work. I don't know how anyone can even argue with me about category theory, I just want to put it off on them being disingenuous instead of thinking about it further or trying to argue with them.
When I see that replies about Chomsky Hierarchy being "extremely useful" and "not very useful" in the same sentence, while I'm downvoted for suggesting otherwise.. Obviously, other commentators need to get their opinion straight before trying to impress their opinion upon mine.
Wow, I actually think you are trolling. I never thought that trolling HN about obscure technical concepts would be a worthwhile use of someone's time.
Just in case you're not, and in case anyone else is following along at home, here is my position.
The Chomsky Hierarchy draws three distinctions or boundaries between grammars:
1. type-0 (unrestricted, recursively enumerable) vs type-1 (context-sensitive)
2. type-1 (context-sensitive) vs type-2 (context-free)
3. type-2 (context-free) vs type-3 (regular)
Distinction 3 is a deep and practical concept that all programmers should know. Distinction 1 is practically useless. Distinction 2 is actively misleading.
Also, when Chomsky developed this hierarchy it was in the context of natural language. He was trying to generate English sentences, not programming languages (which were still rather primitive in 1956 when Chomsky wrote his paper). It is not surprising that most of Chomsky's hierarchy is of limited use to Computer Science, since it was never intended to be.
Not the grammars per se, but the notion that there are things computer programs cannot do -- and that we have a good handle on what these things are -- is an important one.
As for Chomsky's Type 1, I've seen no evidence that the concept of a context-sensitive language has been of practical use to anyone, ever. It looks like an idea that turned out to be a dead end.
EDIT. To clarify: Certainly there are CSLs that have been of practical use. But the fact that a certain language is or is not a CSL, does not seem to be something worth knowing.