I’ve never been able to wrap my head around the concept of the Chomsky Hierarchy. Whenever each level is explained, I just don’t see what it’s telling me. Can someone please?
In: 1
It’s basically a way to classify formal languages (sets of strings) by their complexity.
The more complex a language is the more complex the pattern it can produce.
Regular language are the simplest ones (non-extended regular expressions), they are, among other things decidable: For any string, you can always tell whether it’s part of a given regular language or not. You can always tell with 100% certainty whether a string is accepted by a regular expression.
Context-free languages are a bit more complex, but they are still nicely behaved enough. Most actual programming languages are context free. Parsing them is easy enough and still decidable, while allowing enough of flexibility.
Context-sensitive languages are getting harder to parse, several programming languages and nearly all natural languages are context sensitive languages.
Recursively enumerable languages are the last layer of the hierarchy. Basically, you need a full on Turing machine to parse them. That includes the possibility of infinite loops.
Latest Answers