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:
Happy Little Trees: X' Theory - • Syntactic Trees and X'...
Trace Evidence: Syntactic Movement - • Syntactic Movement and...
Last episode:
Quantifying Sets and Toasters: Generalized Quantifiers - • What Does "Most" Even ...
Other of our syntax and morphology videos:
Raising the Bar: Raising and Control Verbs - • What Changes in a Sent...
Organizing Meanings: Morphological Typology - • Systems of Morphemes
Referential Treatment: Binding Theory - • Binding Theory and Int...
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:
- Their episode on the hierarchy: • Chomsky Hierarchy - Co... .
- Their episode about finite-state machines: • Computers Without Memo... .
- And their episode about how finite-state machines relate to grammar: • Same Story, Different ... .
Find us on all the social media worlds:
Tumblr: / thelingspace
Twitter: / thelingspace
Facebook: / thelingspace
And at our website, www.thelingspac... !
You can also find our store at the website, thelingspace.s...
Our website also has extra content about this week's topic at www.thelingspac...
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)
(4) Evidence Against the Context-Freeness of Natural Language (Stuart Shieber - www.eecs.harvar...)
(5) en.wikipedia.o...
(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*.
Now, let L = {a^nb^mc^nd^m | n ≥ 1 and m ≥ 1}. Suppose L is a context-free language, and let p be the pumping length referred to in the pumping lemma for context-free languages (en.wikipedia.o.... Consider the string z = a^pb^pc^pd^p. Let z = uvwxy satisfy the conditions of the pumping lemma. Then as |vwx| ≤ p, vx can contain at most two different symbols. Furthermore, if vx contains two different symbols, they must be consecutive, for example, a and b. If vx has only a’s, then uwy has fewer a’s than c’s and is not in L, a contradiction. We proceed similarly if vx consists of only b’s, only c’s, or only d’s. Now suppose that vx has a’s and b’s. Then uwy still has fewer a’s than c’s. A similar contradiction occurs if vx consist of b’s and c’s or c’s and d’s. Since these are the only possibilities, we conclude that L is not context-free.
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.

[@helloitismetomato]

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

[@user-uv8xl1qq8g]

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

[@jessicabragg5261]

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! ❤

[@victorli5846]

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.

[@thelingspace]

+Pakanahymni Hmmm. Do you feel that this has changed over time? I think we may generally be quieter overall, but if it's gotten more so, it could be in part a consequence of some of the adjustments we made with how we're recording the audio track. I can look into this more either way, though. There's probably something we can do that will make it somewhat louder without making it weird otherwise. Thanks!

[@vlntnkm]

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

[@kamilziemian995]

Very interesting video.

[@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?

[@thelingspace]

+Philip Gill Yep! Although sorry it took so long to get back to you. But that's definitely a question worth exploring! To start, linguists tend to use the word "grammar" in a way that's different from more everyday definitions, where it might mean anything from spelling to word choice to punctuation. Generally, we use it to refer to whatever speakers know when they know a language, and it can encompass everything from which sounds we use and how they're put together (phonology), to how we construct our words (morphology) and meanings (semantics). In this video, we focused in on a pretty narrow definition: how people put their sentences together (syntax). So "grammar" in our terms here is basically linguistic knowledge writ large. But while we only really had time to talk about syntactic rules, there are absolutely rules in those other systems, too. Like, there are rules that tell us when one sound can change into another, or when we should pronounce a word this way or that. In fact, we can even apply the same questions we talked about in the episode to these other systems; for example, many of the rules that researchers have come up with in phonology are also "context-sensitive", in that a sound might only undergo a change in a specific context. So, even though the ideas in this episode are usually talked about in terms of syntax, they definitely also extend over into other the other domains, too!

[@StereoHistory]

Thank you, that's much clearer.

[@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?

[@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

[@marcinopacki]

Great video. Worth a sub.

[@blastedfish]

Awesome!!!

[@thelingspace]

Thanks! Glad you liked it. ^_^

[@mikelmendizabal8177]

Zorionak! 10.000 ikusle

[@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.

[@charlieangkor8649]

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.

[@Yotanido]

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

[@thelingspace]

+Yndostrui Yeah, I actually think that it's probably better known over in computer science than it is in linguistics. It's an interesting concept. ^_^

[@frankharr9466]

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

[@user-lw8qy8kj7c]

Do Ithkuil and Lojban use type 0 grammar?

[@sugarfrosted2005]

I don't know those languages, but almost assuredly not. C++ and Perl are properly type-0 languages though. You don't really want a properly type-0 languages because not being able to tell if a given phrase is valid or invalid in general isn't a property you'd want. (To be a smart ass, yes they are type-0 languages, but not properly type-0, as A is type-1 implies A is type-0)

[@sugarfrosted2005]

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.

[@AlexanderBollbach]

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

[@thelingspace]

+Alexander Bollbach I don't know! We didn't conspire with anyone to produce more Bletchley Parks, that's for sure.

[@AlexanderBollbach]

n they just gave out the turing award mayb thats y

[@thelingspace]

+Alexander Bollbach Yeah, could be! ^_^

[@GuilhermeTeixeira]

This one was savage.

[@PeterAuto1]

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

[@notoriouswhitemoth]

I'm sorry but... some of your key terms don't seem very well defined here. One important question: what does the arrow actually mean?

[@thelingspace]

+notoriouswhitemoth Sure, let's unpack that more. So, we could have just as easily used the equals sign, but traditionally these kinds of rules use arrows instead. They tell you how certain symbols can be rewritten or analyzed as other symbols. So, a rule like "S → NP VP" just means that the symbol "S" can be replaced with an "NP" and a "VP", which is just another way of saying that a sentence is made up out of a noun phrase and a verb phrase. Other rules come in later and replace that "NP" and "VP" with other symbols, until eventually we're just dealing with the actual words of the sentence, like "the" and "apple" and "fell". So, the rules let us generate whole sentences from simpler symbols, like "S". Collectively, these rules make up the grammar of a language, which can consist of many - even infinitely many - strings of words, which we then call the sentences of that language.

[@notoriouswhitemoth]

+The Ling Space Thank you very much! You may have noticed I have an intense interest in linguistics (also mathematics and several other fields of academics), and I find it frustrating how often things are explained in ways that make them so technical they're next to impossible to learn.

[@katjathesaurus3800]

intention indication culmination thy mention ...

[@sugarwarlock]

+notoriouswhitemoth Formal grammar can be really complicated. If you want to know more, I'd suggest you check out formal grammar in computer science. You can find grammar definition for literally every programming language and it's more mathematical. You can build deterministic automates from grammar, for example. That's basically just a graph. As somebody who studies computer science, this whole video was very easy to understand.

[@sugarwarlock]

+The Ling Space Actually there is the BNF or EBNF ((extended) Backus-Naur Form) that is used in computer science that uses ::= instead of an arrow (and the EBNF also allows =, I think) since you had to write a lot of the grammar in ascii documents back in the days and the arrow is kind of in the way. It's just an easier way to parse it.

[@charlieangkor8649]

What about the Khmer language? Seems to me like Khmer doesn’t have any grammar.

[@mikelmendizabal8177]

Oso ona! Asko ikasi dut. Eskerrikasko

[@Sillilesshells]

I wander which type Finnish would be?

[@juliusjarvensivu5874]

Finnish would most likely fall into Type-2 languages due the permutation of clauses.

[@azforthlol]

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

[@thelingspace]

+Techne Thanks! Glad you liked the video. We'll keep trying to play with the audio, too.

[@katjathesaurus3800]

relevance disturbence coherence propertary attendence

[@mikelmendizabal8177]

Thus we can say that there are some languages more complicated than others. Is Swiss German, with all its rules, more complicated than English? Well, English is an extremely simple grammar language. Probably that is one of the reason it has been so successful. Anybody can learn it and this does not happen with many other languages.

[@chimanruler15]

"Probably that is one of the reason it has been so successful." By that logic, other widely spoken languages such as Mandarin and Spanish must be easy, too, yet there are people who insist that they are not. That's not why English is widely spoken. English is widely spoken because the US is one of the most influential countries in the world. "Well, English is an extremely simple grammar language." Not really. I say this because most people are unable to speak with perfect grammar most of the time. Even your comment has grammar issues. "Anybody can learn it and this does not happen with many other languages." You mean like Spanish, Mandarin, Portuguese, German, Hindi, Arabic, etc.? These are widely spoken languages, too.

[@robert_wigh]

6:37 I’m currently learning German and I can tell you for sure, that isn’t German. I looks more like French, in some ways. d’Marie, d‘chind...what is that? Das ist kein Deutsch!

[@seamusmcrae414]

Robert Andersson he said it's Swiss German, which has more evident Romantic influences than standard German does

[@robert_wigh]

Seamus McRae Yes, I heard what he said just as well as you did. I made my comment to make a point: German, just as Arabic, is not a unified language but it has many different dialects, just like this one and Low German (_Plattdüütsch_) and I would not consider German at all. I strongly think they are dialects that have evolved so far from the standard German of Germany that they can not be called ‘German’ anymore...on the other hand, that‘s just my opinion. Was finden Sie diese Dialekten der deutschen Sprache? Ist „Schweizerdeutsch“? Deutsch or nicht? Ist „Plattdeutsch“ Deutsch oder nicht? Ich finde, dass sie andere sprachen als Deutsch sind.

[@KhlavKalash11235]

As a native German speaker I would say, that at least in this example, Swiss German isn't all that different from standard German. The words look weird, but when you read them out aloud, the same as in standard German. The only really different part are the verbs at the end. In standard German they would be in the exact opposite order, so there wouldn't be these Crossing Dependencies. But these kind of sentences are basically not understandable in any dialect of German because of the way all the verbs cluster together at the end. I actually had a pretty hard time figuring out how I would say this sentence in standard German. I would defenetely say that Swiss German is German. Because German has always been made up of many dialects, which can be very different. Standard German actually only started existing to make it easier for speakers of different dialects to understand each other (at least as far I know, I am not an expert). So I would say that at least all German dialects are German even if they are very different from Standard German. I read that Low German can be considered its own language. But even then I would still say that it is German. Only that there are two German languages High German and Low German, and that both are in turn made up of many different Dialects. But remember, as I said, I am no expert on any of these things, I am just pretty interested in languages and espacially in the different dialects here in Germany. I hope that this text is understandable. English isn't my first language and these kinds of texts are hard with all the long sentences.

[@robert_wigh]

Khlav Kalash Genau, perfectly understandable. Almost perfect, except that you misspelled *definitely*. :)

[@UrbaNSpiel]

Can't hear. Make video louder...

[@RodolfoVasquesvideos]

TRY TO SPEAK MORE SLOWLY, PLEASE!!!

[@dhiyaneshsivakumaran9201]

Hey! you are not speaking English but singing English. It's like hearing a railway gate open from metres away.