How Complex is Natural Language? The Chomsky Hierarchy

How can we describe the complexity of linguistic systems? Where does natural language fit in? In this week's episode, we talk about the Chomsky hierarchy: what it captures, what characterizes different kinds of grammars on the hierarchy, and whether we can find grammars that sit higher on the scale than human language.

This is Topic #63!

This week's tag language: Croatian!

Related topics:

Last episode:

Other of our syntax and morphology videos:

Also, if you'd like to know more about the Chomsky Hierarchy and its impact on computer science, Computerphile's had a few videos about them:

Find us on all the social media worlds:

We also have forums to discuss this episode, and linguistics more generally.

Sources:
(1) I-Language (1st Edition, Daniela isac & Charles Reiss)
(2) Introduction to the Theory of Computation (3rd Edition, Michael Sipser)
(3) Mathematical Logic for Computer Science (3rd Edition, Mordechai Ben-Ari)
(6) Syntactic Structures (Noam Chomsky)
(7) Mathematical Methods in Linguistics (Barbara Partee, Alice G. ter Meulen, Robert Wall)

Proof regarding crossing dependencies (adapted from the first edition of Introduction to Automata Theory, Languages, and Computation, by John Hopcroft and Jeffrey Ullman. Note where carets appear that the following character should be taken as superscript):

We first capture the general pattern of embedded clauses in Swiss German with the language a^nb^mc^nd^m . We then treat this as the result of intersecting Swiss German with the regular language a*b*c*d*.

Since context-free languages are closed under intersection with regular languages, and the above intersection is not context-free, Swiss German must be non-context-free.

Q.E.D.

A proof of the pumping lemma itself can be found in Introduction to the Theory of Computation (among other places). For a discussion of the closure properties of context-free languages, see Mathematical Methods in Linguistics (among other places).

Looking forward to next week!

[Artoonie]

There's a lot of negativity in these comments so I wanted to say thanks for helping me decipher the wikipedia page on The Chomsky HIerarchy. This video gave a good explanation of the syntaxes used to explain grammers and primed my learning with an easy-to-understand framework.

[jessicabragg]

So it's 2022 and I just want to say HOW HELPFUL this has been! I literally looked up a basic explanation for this for like an hour and yours is actually a basic explanation and not just repeating definitions from a web page. I actually understood most of this fully.

So thank you for helping me get one step closer to graduation! ❤

[랙쇼랙쇼]

Thank you for easy explanations! I know nearly nothing about automata theory and Chompsky hierarchy, which kept me from understanding what they are talking about. Now I get a sense

[helloitismetomato]

Support and love to the two guys who got married on the top left shelf in the shot

[victorli]

Thank you so much, I am not linguistic but working on natural language. It really helps me compared to those super complicated videos!

[arsnakehert]

Nice to see how this applies to actual natural language outside what we study computer science. In CS we handle formal languages with "words" being symbols and "phrases" being words, so we usually have an alphabet of a's and b's, or 0's and 1's, which gets abstract really fast. It helps reasoning about these constructs abstractly without getting caught up in the significance of e.g. the variables, though.

[Pakanahymni]

I watch lots of youtube and I always notice how much quieter your videos are compared to others. With my settings I turn the volume down in crash course videos but here I turn the player to the max and I think it's still not quite enough.

[vlntnkm]

This helped me a lot with my presentation!! Thank you

[frankharr]

I've always liked how "below" is indicated.

[Yotanido]

The Chomsky scale and formal grammar. Something I knew already, for a change. :D
(I study computer science)

[Coconutoilcrazy]

While searching to understand and how to syntax Quantum grammer, this video came up- what is the reason for all of this? Different writing styles? Formal/Informal?

[JayFolipurba]

Like my favourite sentence in German that I made up and it's only half a sentence:
(e.g. Es besteht kein Zweifel), dass das das Das das *das* Das ist ist.
Or rather: Es besteht kein Zweifel, dass dies jenes Das ist, welches das besagte Das ist.

[StereoHistory]

The piece starts by mentioning systems but doesn't make clear the difference between syntax and grammar, yet these two terms seem to be used interchangeably throughtout the presentation. Can you help?

[PeterAuto]

It's funny that Chomskey Hierarchy is directly related to computability and therefore teached in Computer Science courses.

[arsnakehert]

Does this "uselessness"of type-0 languages have to do with introducing the possibility of infinite loops when trying to recognize phrases in them? Because, if I'm not mistaken, that's what they introduce in formal languages – they're the languages that can be decided by Turing machines, along with the ones that cannot

[charlieangkor]

Please make a video how to actually wire a neural circuit to produce real natural language. I tried to do it but it was full of language pathologies the output was not a normal natural language.

[sugarfrosted]

8:40 "[Using type-0 languages] just doesn't compute" I see what you did there. iirc type-0 is recursively enumerable. I can eventually tell you if it's valid, but I can't tell you if it's invalid in general.

[がに-kn]

Do Ithkuil and Lojban use type 0 grammar?

[AlexanderBollbach]

thats the 3rd time i've heard bletchley parkin 24 hours, what is going on?

[azforthlol]

Good video but please take it down an octave or at least decrease the treble and increase the bass on your mic.