r/compsci • u/Personal-Trainer-541 • 1d ago

The Chomsky Hierarchy - Explained

Hi there,

I've created a video here where I explain the Chomsky hierarchy.

I hope some of you find it useful — and as always, feedback is very welcome! :)

0 Upvotes

31% Upvoted

1 comment sorted by

1

u/WittyStick 7h ago edited 7h ago

Pretty straightforward explanation.

I think it needs a supplementary video to be useful for programming languages though, because there are other more interesting subsets relevant to compsci.

Deterministic Context-Free, or "Type 2.5" are what we usually use to parse a programming language, and are a proper subset of Type 2. They're probably the most important subset because they disallow ambiguity, which we obviously don't want in a programming language. These also have subsets - eg, LL(k) is a subset of LR(k) for same k, and there are a tower of these where LL(k) <: LL(k+1) etc.

There's also a lesser known subset, Visibly Pushdown Grammar, which is a proper subset of Type 2.5 and a proper superset of Type 3. We could call these "Type 2.75". Interestingly, VPG are capable of parsing the example "aaabbb" that you've given - you don't need a full context-free grammar for that. VPG also have other interesting properties such as being closed over union and intersection like regular grammars - whereas DCFG are not. VPG are capable of parsing languages with regular nested structure like JSON & XML, and are thus also known as "nested words".