EPISODE TRANSCRIPT
Formal Properties of Grammars (Noam Chomsky)
Automatically transcribed from the episode audio. Some words and names may be inaccurate.
Listen to the episodeDownload textDownload captions
You know, usually when we talk about human language, there is this expectation of, well, organic messiness. Right. We tend to view language through like. a biological lens. You think of it as this living, breathing, evolving organism that shifts with culture and slang and historical migrations. Absolutely. It feels very tied to sociology. Yeah, exactly. You point to a weird grammatical quirk in English, like how the plural of goose is geese, but the plural of moose isn't meese.
And you just shrug and say, well, that's just how people talk. It's human nature. It feels incredibly fluid from the inside. Like when we speak. We certainly don't feel like we are solving equations. You know, we feel like we are just expressing this chaotic stream of consciousness. Right. It is the absolute definition of organic chaos. But then you step into the world of theoretical linguistics and early computer science, and suddenly that biological messy lens is completely shattered. Oh, completely. It's a total paradigm shift. We are no longer looking at a cultural artifact or a sociological phenomenon. We are looking at a machine. like a cold, hard calculating machine.
And that shift in perspective is, it's jarring for a lot of people at first, but it is necessary. Really necessary. But to truly understand the underlying architecture of how we communicate, we have to look at language as a rigid, formal system governed by absolute laws. We have to treat words and sentences as nothing more than strings of symbols subject to strict mathematical operations. And whether you are a computer scientist trying to build the next generation of artificial intelligence or maybe a linguistics nerd or just insanely curious about how the human mind actually organizes its thoughts before you even open your mouth, today's deep dive is going to fundamentally change how you see every single sentence you speak. I really believe it will. The text we're looking at today is just that important. It really is. Today, we are opening up a truly foundational text. We are looking at Noam Chomsky's 1959 paper on certain formal properties of grammars. The impact of this specific paper is, frankly, difficult to overstate. It sits squarely at this intersection of information theory, computer science, and linguistics. Because before this era, linguistics was largely about categorizing words almost like botany you know like collecting specimens of language and pinning them to a board just labeling things noun verb adjective exactly but this paper this paper translates the architecture of the mind Into algebra. Okay, let's unpack this. Our mission today is highly ambitious. We are going to break down this notoriously dense, mathematically rigorous paper concept by concept. We're going to trace the dependencies, explore the general theories, and we are going to translate these heavy symbolic theorems into intuitive aha moments.
That's the goal. Right. We want to understand the exact mathematical boundaries of human thought without getting lost in the chalkboard equations. So to start us off, if we are treating language like a machine, how do we even define what a language is? Well, the foundational definition here requires us to strip away all meaning, emotion, and context. Which is hard to do. It is. But mathematically speaking, Chomsky defines a language simply as a collection of sentences. And each of those sentences is a finite length, constructed from a finite alphabet, or a finite vocabulary of symbols. Okay, let me pause there just to make sure I'm visualizing this correctly. The finite part makes sense. I mean, the English dictionary is thick, but it's finite. There's a set number of words. Right. And the alphabet is finite 26 letters. And any single sentence I speak has to be finite in length, if only because I eventually have to stop talking to take a breath.
The physical constraints are finite, yes. But here is the paradox that really drives the entire field of cognitive science. Any language we actually care about studying, whether that is English or Mandarin or a programming language like Python, is fundamentally an infinite set of sentences. Because I can always just make up a brand new sentence that has never been uttered in the history of the universe. Exactly. I could say the purple walrus tap danced on a quantum computer made entirely of expired Swiss cheese. And boom, that is a brand new syntactically valid English sentence.
It is. And you could theoretically add and then to the end of that sentence over and over again, extending it forever. So the set of all possible English sentences is infinite. Right. But the human brain, the actual organ that somehow contains and processes this language is a finite. physical object. It has a finite number of neurons. So the fundamental question is, how does a finite device manage an infinite set? Because we obviously don't just have an infinite list of sentences memorized in our heads. We couldn't possibly.
There isn't enough storage space. Yeah. Therefore, we can only investigate the structure of this infinite language through the study of finite mathematical devices capable of enumerating its sentences. Enumerating meaning like generating them one by one. Yes. We need a finite set of rules that can generate the infinite possibilities. And Chomsky refers to these finite generating devices as grammars, which I think is a term we need to redefine for you, the listener, right now. Oh, definitely. Because when I hear the word grammar, I immediately think of my middle school English teacher telling me not to end a sentence with a preposition or, you know, scolding me for splitting an infinitive. Yeah, we have to completely discard that prescriptive definition.
A grammar. in this formal mathematical sense, is not a rule book of etiquette. It is a function. A mathematical function. Think of it as a mechanical engine. It's a generative device that takes integers as inputs and outputs, valid sentences in the language. The entire infinite language is just the mathematical range of this grammar function. Okay, so we need a machine that spits out sentences. But if all we want is a machine to generate every valid English sentence, couldn't we just use the most powerful computer imaginable, like a general unrestricted Turing machine? Well, a Turing machine can simulate any computer algorithm in existence. It is the absolute ceiling of computational power. If you can program a rule, a Turing machine can execute it. Right. So, yes, theoretically, a Turing machine could easily be programmed to spit out valid sentences in a language. But reading through the introduction of the paper, Chomsky seems to aggressively dismiss that idea. He essentially says that if our grammar is just a general Turing machine, it is completely useless to us. Why would the most powerful machine be useless? The issue is transparency. A Turing machine is a black box. A black box. It might... perfectly enumerate this set of all valid sentences, but it tells us absolutely nothing about the underlying structure of those sentences. If we want a true scientific theory of language, the theory must provide what Chomsky calls a structural description.
I want to make sure I grasp this difference between generation and structural description. Let me try an analogy here. Go for it. Imagine I have a magical black box that builds houses. I press a button on the side of the box. It rumbles and out pops a perfectly built, fully furnished, structurally sound house. That's our Turing machine, right? It's generating the language of houses perfectly. That fits the model. Yes. Yeah. The output is perfectly valid. But if I'm an architect or like a civil engineer, that magical black box teaches me absolutely nothing about how to build a house. It doesn't give me a blueprint.
It doesn't tell me that the concrete foundation has to be poured before the walls go up. or that the roof's weight has to be distributed across load -bearing beams. It just gives me the final product. That is a phenomenal way to visualize it. Yeah. Chopsky is demanding the blueprint. He argues that just generating the sentences isn't enough. The theory must include a functional vi, which he labels with the Greek letter phi, that applies to the grammar and the sentence to yield that structural description. Why is the blueprint so important, though? I mean, if the machine works, why do we care how it works?
Because that structural description is the only way to explain how a human speaker or hearer actually understands a sentence. A flat string of words doesn't contain meaning on its own. The meaning is derived from how those words relate to each other. The blueprint tells us how to resolve ambiguities. It shows us why two sentences that look very different might actually share the exact same underlying structure. Right, right. Without the blueprint, you don't have language comprehension at all. You just have a parrot repeating noises. Which feels incredibly relevant today. I mean, if we look at what is happening right now in the world of artificial intelligence and large language models, this is the exact debate we are having. Oh, the parallel is striking.
We have these massive AI chatbots that can output perfectly valid, highly... eloquent paragraphs. They act like incredibly powerful Turing machines enumerating sentences. Yes. A language model predicts the next word with astonishing accuracy, generating a beautiful output. But linguists and cognitive scientists are asking Chomsky's exact question from 1959. Does this machine actually possess a structural description? Exactly. Does it have the blueprint or is it just a statistical black box? Chomsky was warning us over 60 years ago. that enumerating the set of sentences is the easy part. The true mystery, the theoretical gold, is in the internal architecture of the structure. That is wild. Generating text is cheap understanding structure is everything. So if a Turing machine is too much of a black box, we need to design a different kind of machine, one that is slower, more transparent, where we can watch it lay every single bit of the sentence.
How do we build that? Well, to get away from the black box, we need a system that builds sentences step by step in a highly restricted way that leaves a visible trace. Chomsky introduces a basic mathematical system for this, which he calls a semi -group under concatenation. Semi -group under concatenation. That sounds like a terrifying college course I would drop on the first day. How do we translate that into plain English? The terminology is dense, I know, but the concept is very straightforward. A semi -group in this context just means we have a collection of symbols. Okay. And concatenation is simply the mathematical operation of linking things together in a chain or series. So we are just smushing symbols together side by side. If I have symbol A and symbol B, I concatenate them by just writing AB. That is literally all there is to it. The system operates entirely by sticking symbols next to each other. Now, this system has a vocabulary, which we'll call V, and Chomsky makes a crucial distinction by splitting this vocabulary into two totally different categories.
Okay, what's the first one? First, we have the terminal vocabulary. Terminal meaning, like, the end of the line. Right. These are the actual final words or morphemes of the language. If we are modeling English... The terminal vocabulary consists of words like John, comes, the apple, running. When you hit a terminal symbol, you can't break it down any further within the grammar. Okay, makes sense. What's the second category? The second category is the non -terminal vocabulary. These symbols never actually appear in the final spoken sentence. Oh, interesting. Yeah. They are abstract structural placeholders. These are your grammatical categories, things like noun phrase, verb phrase, adjective, or even just the abstract concept of a sentence. So if I'm looking at a blueprint of a house, the terminal symbols are the actual two by fours, the nails and the drywall, the physical stuff. And the non -terminal symbols are the abstract labels on the blueprint, like master bedroom area or kitchen wall. You can't physically touch a kitchen wall concept, but you eventually fill it in with actual drywall and paint. A perfect extension of the analogy. Now, to make this machine actually do something, it needs a motor. And the motor of this grammar is a finite set of rewriting rules. Rewriting rules. Yes. In the mathematical notation, a rule looks like this. You have a string of symbols, an arrow pointing to the right, and another string of symbols. So X arrow Y, meaning wherever I see X, I am allowed to erase it and rewrite it as Y. Exactly. But to maintain absolute mathematical rigor, Chomsky doesn't just let us make up whatever rewriting rules we want. He establishes four strict axioms that govern how these rules can operate. These axioms are kind of like the laws of physics for our grammar machine. I want to dig into these because reading through the paper, the axioms felt almost painfully obvious at first glance, but I suspect there is a deep mechanical reason for each of them. There absolutely is. Let's take the first one. Axiom one states that the rewriting relation is irreflexive, meaning you cannot have a rule that simply rewrites a symbol as itself. You can't have A arrow A. Why even bother making that a rule? Who would write a rule that does nothing? Think about it from the perspective of a literal unthinking machine or a computer program trying to resolve a process. If the machine encounters the symbol A and the rulebook says you must rewrite A as A, what happens? The machine replaces A with A, then it looks at the new A, consults the rulebook, and the rulebook says rewrite A as A. Oh, I see. It's an infinite loop.
Precisely. The machine freezes. It just sits there forever rewriting the same symbol. The system would crash. A generative grammar must always be moving forward, making progress toward a final terminal string. An irreflexive loop halts all progress. So axiom one prevents the machine from freezing. Okay, that makes perfect sense. What about the next one? Axiom two is a defining boundary. It states that a symbol belongs to the non -terminal vocabulary if and only if there is at least one rule that rewrites into something else. So if a symbol can be broken down, it's non -terminal. If there is no rule to break it down, it's terminal. The mathematical consequence of that is profound. It means the machine knows exactly when its job is done. When the string contains only symbols that have no rewriting rules associated with them, the derivation naturally terminates. Without Axiom 2, the machine wouldn't know the difference between an abstract noun phrase marker and the actual word apple.
It might try to keep breaking down the word apple into smaller pieces indefinitely. It's the mechanism that tells the machine, stop, you've hit the bedrock, the sentence is finished. I love how physical this feels. There are also two special boundary symbols in the vocabulary represented by hash marks, like a hashtag. What do those do? The boundary symbol hash is crucial for defining the edges of the universe we are working in. Axiom 3 dictates that you can never erase these boundary symbols from the left or right ends of the string. And you can never insert a new boundary symbol into the middle of a string.
They are sacred borders. They tell the machine, this is where the sentence begins and this is where it ends. Do not build outside this property line. Exactly. And the final axiom, axiom four, just guarantees that our set of rewriting rules is strictly finite. Right. Which ensures we are still dealing with a finite device as we established in our foundational problem. So with these laws of physics in place, let's actually run the machine. Let's do it. Let's look at a derivation sequence step by step using a simplified version of Chomsky's own example. I want to see the bricks being laid.
Okay, we always start with the most abstract, highest level symbol possible. The initial string consists of a left boundary mark, the symbol S for sentence, and a right boundary mark, hash, S, hash. Okay, we have our property lines, and right in the middle is just a giant sign that says a sentence will go here. Now the machine consults its rulebook. It finds a rule that says S can be rewritten as A followed by B. So the machine applies the rule. Our new string is hash, A, B, hash. And let's ground those abstract letters.
In Chomsky's example, A is the non -terminal symbol for a noun phrase and B is the non -terminal symbol for a verb phrase. Correct. So our abstract sentence has now been split into a noun phrase and a verb phrase. And the machine keeps going. It finds a rule for A. The rule says A rewrites as C. where C stands for singular noun. So the string is now hash, C, B, hash. We have a singular noun and a verb phrase. It's getting more specific. Yes, the machine looks at B. The rule book says B, the verb phrase, rewrites as a terminal lowercase symbol B. Let's say this terminal symbol B is the actual English word comes. Oh, so we've hit bedrock on the right side of the sentence. The string is now hash, C, lowercase B, hash or hash.
Singular noun comes hash. Almost done. One step left. The machine looks at C. The rule says C rewrites as the terminal lowercase symbol A. And let's say A is the word John. The string is hash, AB, hash, hash, John comes, hash. Yes. We've hit terminal bedrock across the entire string. There are no more non -terminal symbols to rewrite. Axiom 2 kicks in, the machine halts, and we have our sentence. We have successfully generated a sentence. But remember our critique of the Turing machine. Right. Generating the output is only half the battle. Exactly. We demanded a blueprint. We demanded a structural description that explains how the sentence was built. So where is the blueprint? Well, I would normally think that once the sentence is printed out, a linguist would come along, read John comes, and draw a little diagram on a talk board pointing out that John is a noun and comes is a verb.
That is how humans usually do it after the fact. But the genius of Chomsky's formalization is that the blueprint created itself. Wait, really? Yes, because we started with a single symbol S. and strictly followed rules that replaced one symbol with others, this linear sequence of string replacements automatically maps out a mathematical structure called a labeled tree. Oh, like a family tree or a corporate organizational chart. Exactly that. So the S is the CEO at the top. The S splits into two vice presidents, A and B. The vice president A manages a director named C, who manages a frontline worker named John. Vice president B manages a frontline worker named Cums. That hierarchy is the structural description. In traditional linguistics, drawing that tree is called immediate constituent analysis.
What Chomsky proved here is that the tree is not a subjective diagram drawn by a linguist interpreting a sentence. The tree is literally just the exhaust fumes of the machine. Yes. It's the chronological history of every single decision the rewriting machine made. The structural description is identical to the generative history of the sentence. If you know the exact sequence of rewriting rules the machine used, you have mathematically defined the grammatical structure of that sentence. It removes all human subjectivity from grammar.
It is pure, traceable mathematics. That is an incredible aha moment. The act of building the sentence is the grammar of the sentence. Right. Okay, so now we have this brilliant transparent machine called a phrase structure grammar that gives us both the sentence and the blueprint. But Chomsky doesn't start there. He takes this machine and starts tinkering with its engine, which brings us to one of the most famous concepts in all of computer science, the Chomsky hierarchy. Yes. Having established the basic mechanics of how rules rewrite strings, Chomsky asks a crucial scientific question. What happens to the generative power of this machine if we start artificially restricting the types of rewriting rules it is allowed to use? He creates four distinct levels of power from a completely unrestricted free -for -all down to a highly constrained, rigid system. Theorem 1 formalizes this nested hierarchy.
Type 0 includes type 1, which includes type 2, which includes type 3. Let's define the boundaries of these levels. We already discussed the top level, type 0. This is the unrestricted Turing machine. Right. In type 0, there are absolutely no restrictions on the rewriting rules. You can rewrite any string of symbols into any other string of symbols in any order with no oversight. It can compute anything the universe allows to be computed. But as we discovered, that absolute freedom destroys our ability to easily extract a clean structural tree. The derivations can be so chaotic that the history is useless. So we impose a mathematical restriction. We create type 1 grammars. These are formally known as context -sensitive grammars. Context -sensitive.
The name implies that the machine has to look at its surroundings. How is that written mathematically in the rule book? The restriction mandates that every rule must take a specific form. I'll read the notation and it'll translate it. Phi 1, A, Phi 2, arrow Phi 1, omega Phi 2. Okay, let's break that down into physical actions. A is our single non -terminal symbol. Let's say it's our noun phrase. Omega is the new string of symbols we want to replace A with. But what are the Phi symbols on either side? Think of phi 1 and phi 2 as the context. The rule states that you are only allowed to transform A into omega if and only if A is sitting exactly between the string phi 1 on its left and phi 2 on its right. Oh, I see. It's like A is trying to get into an exclusive nightclub and Omega is the VIP section. The rule says A can only transform and get into the VIP section if it brings two specific bouncers with it. That's a great way to picture it. If the left bouncer, Phi 1, and the right bouncer, Phi 2, aren't physically standing next to A in the string, the rule doesn't trigger. A is stuck.
That is an excellent visualization. The context surrounding the symbol dictates whether the transformation is legal. That is the essence of a type 1 grammar. But what if we want to restrict the machine even further? What if we fire the bouncers? Okay, moving down the hierarchy. That brings us to type 2 grammars, universally known as context -free grammars. Context -free, so the rule gets simpler. Much simpler. The restriction for type 2 simplifies the rule format down to just. A arrow omega. No bouncers. The context is completely null. The symbol A is rewritten entirely independently of its surroundings. It does not matter what symbols are sitting to the left or the right of our noun phrase. The rules for how a noun phrase can be expanded into smaller components remain exactly the same regardless of where it appears in the sentence. And then at the very bottom, we have the most mathematically restrictive level, type three, which are called finite state grammars. How strict do the rules get here? Extremely strict. Restriction three says that a non -terminal symbol can only be rewritten in one of two very specific ways. Either A rewrites as a single terminal lowercase, A followed by exactly one single non -terminal capital B, or A simply rewrites as the single terminal lowercase a. So if I'm tracing the tree. Every single time a node branches, it immediately spits out one final terminal word and leaves exactly one abstract symbol to be processed next. It's a completely linear one -way progression. It forces the derivation to move strictly from left to right one word at a time. It's the simplest possible generative mechanism. So we have this beautiful, clean hierarchy.
But Chomsky doesn't just name these categories. He uses rigorous proofs to determine exactly what these different machines are capable of. And theorem three is a massive breakthrough. Theorem three proves that each type one language is a decidable set of strings. Right. Now, I know decidability is a huge concept in computability. Why is this theorem such a big deal for us? To appreciate the breakthrough, you have to look at the alternative. With a type zero unrestricted Turing machine, we run into the famous halting problem. First proved by Alan Turing. A halting problem. Yeah. If I hand a type zero machine a random thousand word string of symbols and ask, is this a valid sentence in your language?
The machine might start calculating and never stop. Because it's allowed to do anything. Exactly. It might get caught in a complex web of derivations, constantly expanding and shrinking the string, calculating until the heat death of the universe without ever giving me a yes or no answer. A type zero language is generally an undecidable set. But theorem 3 proves that if we restrict the machine to type 1 context -sensitive rules, the set becomes decidable. Meaning, if I hand a computer a type 1 grammar and a random string of words, I am mathematically guaranteed that the computer will eventually halt and give me a definitive, yes, this is a valid sentence, or no, it is not. Yes. How does Chomsky prove that? What is the mathematical trick? The mechanism of the proof relies on a very subtle but powerful feature built into type 1 rules. Notice that in a type 1 rule, you are replacing a single symbol A with a string omega. Chomsky adds a specific stipulation here. Omega cannot be a null string. It cannot be empty. So whenever you apply a rule, you are always replacing one symbol with one or more symbols. You can never replace a symbol with nothing. Think about the physical consequence of that rule on the string itself. With every single step of the derivation, every time the machine runs, the resulting string of symbols either stays the exact same length or it grows longer. It can never, ever shrink.
Oh, I see where this is going. If it can't shrink, it creates a boundary. Precisely. Let's say you want to test a specific sentence. Let's call it x. And sentence x is exactly 10 words long. Because we know the strings in a type 1 derivation can only grow, we only have to ask the computer to generate all possible derivations that result in strings of 10 words or fewer. Because if a derivation reaches 11 words, it can never shrink back down to match our 10 -word sentence. It's mathematically impossible. Exactly. And because the vocabulary is finite and the length is capped at 10, there is a strictly finite number of possible derivations to check. The computer generates that finite pile of sentences. It looks through the pile. Right. If our sentence X is in the pile, the answer is yes. If it's not in the pile, the machine can confidently answer no. Secure in the knowledge that any further computation would only produce sentences longer than 10 words.
That is so elegant. By forcing the string to only grow, he creates a mathematical ceiling on how far we have to search. The halting problem is solved. The set is decidable. It's beautiful math. It really is. But because Chomsky is incredibly thorough, he drops a massive curveball in the footnotes. Footnote 7a. He proves that while every type 1 language is decidable, the reverse is not true. There are languages out there that are perfectly decidable, but they are absolutely not type 1. Yes. And he proves this using the diagonal language argument. This is one of the most beautiful proof techniques in mathematics.
It was originally developed by George Cantor to prove that some infinities are larger than others. It was adapted by Alan Turing for the halting problem, and Chomsky deploys it here to map the outer limits of type 1 grammars. It's heavy theoretical computer science, but I want to try and walk through it because the logic is fascinating. How do we build a language that is decidable but definitely not type 1? We do it by building a paradox. Let's start with a thought experiment. Assume we can create an effective... ordered infinite list of every single possible type 1 grammar in the universe. We will label them grammar 1, grammar 2, grammar 3, and so on forever. Okay, we have a master registry of every type 1 machine. Now alongside that, we make a second ordered infinite list. This list contains every possible finite string of symbols you could ever randomly type on a keyboard. String 1, string 2, string 3, going on infinitely. So we have two infinitely long lists sitting side by side. The list of machines and the list of random strings. Now, we are going to act as the creators of a brand new language. We will call our language M. We're going to build the rules for what belongs in language M step by step by looking down our two lists. How do we decide what gets into language M? We go to step one, we look at string one, we walk over to grammar one and we ask it, can you generate string one?
Remember, because type one is decidable, grammar one will always give us a straight yes or no answer. Right, it won't freeze. If grammar one says yes, yes, I can generate string one, we ban string one from our new language M. If grammar one says no, I cannot, we welcome string one into language M. So we are acting like a rebellious teenager. We are looking at whatever the grammar on the list does, and we are purposefully doing the exact opposite. A perfect analogy. Then we move to step two. We ask grammar two if it can generate string two. We do the opposite of its answer to define our language M. We go diagonally down the list. Step three, step four, step N.
Always ensuring that our new language M differs from the behavior of grammar N regarding the Nth string. We build this whole language M and then some mathematician comes along and says, hey, your new language M is clearly a type one language. It must be hiding somewhere on your infinite master registry of type one grammars. And how do you prove them wrong? Because if they claim that language M is, say, grammar number 500 on the list, we just look at step 500. By our rebellious definition, language M does the exact opposite of whatever grammar 500 does to string 500. Exactly. Therefore, language M cannot possibly be grammar 500. It cannot be grammar 1 million. It cannot be any grammar on the list because it is designed to disagree with every single grammar on at least one specific string.
The logic is inescapable. Therefore, language M simply does not exist within the realm of type 1 languages. It is outside the boundary. But because we have a clear step -by -step mechanical procedure for deciding exactly what goes into language M, it is by definition a decidable language. It's a mathematical magic trick. We proved a boundary exists by building something that willfully violates it. Okay, so all of this math leaves us feeling pretty incredibly impressed with type 1 grammars. They use context, they solve the halting problem, they are massively powerful.
We should just use type 1 for all human language and call it a day, right? Mathematically, that might seem tempting, but linguistically, it would be a complete disaster. A disaster. Yeah. In section 4 of the paper, Chomsky exposes a fatal defect in type 1 grammars when applied to the actual structure of human thought. Let's break down this defect. But first, to understand why type 1 is flawed, we have to understand why it's so powerful in the first place. Chomsky uses lemma 2 to demonstrate a specific superpower that type 1 has, which type 2 does not. He introduces a hypothetical mathematical language with cross dependencies. This cross dependency language is defined by a very specific pattern of symbols.
The sentences must look like this. A certain number of A's followed by the exact same number of B's. then a repeat of that first number of A's, followed by a repeat of that first number of B's, ending with a string of C's. So A to the power of N, B to the power of M, A to the power of N, B to the power of M, and then C, C, C. Correct. So if I have five A's and three B's at the start of the sentence, I absolutely must have exactly five A's and three B's later in the sentence. It's a matching game across a long distance. And Chomsky proves that a type one context -sensitive grammar can successfully generate this cross -dependency language. Why?
Because the context rules act as a rudimentary form of memory. Right. Because the rules require the machine to look at the bouncers, the symbol standing next to it. The grammar can essentially copy a string of information and carry it across the derivation sequence to reproduce it later. It can look back and say, ah. My context tells me we had five A's and three B's over on the left side of the sentence, so I need to force the right side of the sentence to match. It has situational awareness. Exactly. But theorem four proves that a type two context -free grammar cannot generate this language. Yeah. Think about the definition of type two. The rule is just A, arrow, omega, there is no context. There are no bouncers. The symbol A transforms blindly with no idea what is happening on the other side of the sentence. It has amnesia. It cannot remember that it generated five A's earlier, so it cannot mathematically guarantee it will generate five A's later. So on paper, type one is superior because it has this situational awareness. That is the mathematical illusion. It has more generative power, yes. But remember our foundational requirement from the very beginning of the deep dive. Generation is not enough. We need the structural description.
We need the blueprint, the parsing tree. And here is where type 1 collapses. Lemma 1 proves that the situational awareness of type 1 allows it to perform a very dangerous operation. A permutation. A permutation, meaning changing the order of things. Exactly. Lemma 1 shows that in a type 1 grammar, you can easily create a rule that looks like this. xb arrow bx, you are taking the symbol x and the symbol b, and you are just swapping their positions in the string. Because type 1 allows context, in this case, x acting as a context for b, the machine, can execute this swap perfectly well to generate the final string of words. Okay, let's bring this out of the math and into English to see why this swap is so catastrophic. Let's say our machine is building the underlying structure for a simple declarative sentence. It drops three abstract symbols, a noun phrase, followed by a modal verb, followed by a main verb. And let's say the terminal words for those are John, will, and come. The machine generates the string, John will come.
And if we look at the tree, the blueprint generated by that history, it is perfectly clean. The word John traces straight up to the noun phrase node. The word will traces straight up to the modal note. But now let's say we want to turn that declarative statement into a question. We want to say, will John come? To do this, our type 1 machine uses that permutation rule we just talked about. It looks at the noun phrase, John, and the modal, will, and it swaps them. XB becomes BX. The machine outputs the strain perfectly. The words read from left to right, will John come? The generation was successful. But wait, if I am a linguist trying to understand the blueprint...
The tree is supposed to just be the history of the derivation. So if I trace the lines straight back up from the words in their new positions, what happens? The lines cross. The tree gets hopelessly tangled. Let's trace it. The word will is now in the first position in the sentence. If you trace the lines straight up from that first position, the tree will erroneously label will as the noun phrase. And John, which is now sitting in the second position, will trace straight up and be labeled as the modal verb. Exactly. The tree is lying to us. The blueprint is fundamentally structurally false. Will is not a noun. John is not a modal verb. If an AI used this tree to try and understand the sentence, it would think John was an action you could perform. The extra mathematical power of the type 1 grammar, the power that allowed it to do cross dependencies and permutations, is the exact thing that destroys the structural integrity of the constituent analysis.
The lines cross, the nodes mislabel the words, and the blueprint is useless. So we are caught in a trap. Type 1 is computationally powerful, but linguistically bankrupt. We have to abandon it. We have to step down the hierarchy to type 2, the context -free grammars. Because in type 2, a symbol rewrites entirely independently. The branches of the tree drop straight down. They never cross. The tree stays pure and honest. That is the necessary compromise. Which brings us to a major inflection point in the paper.
We know we have to step down to type 2 to keep our trees honest. But the natural scientific question is, why stop there? Right. Why use a complex hierarchical phrase structure tree at all if we can go even simpler? Why not step all the way down to the absolute bottom of the Chomsky hierarchy? Why not use type 3, the finite state grammars? To rigorously answer this, Chomsky first has to prove exactly what type 3 grammars are. In theorem 6, he proves that type 3 languages are mathematically identical to finite state Markov sources. A finite state Markov source.
I love visualizing this mechanism because it's so intuitive. Imagine a simple board game. The board has a finite number of spaces, or states. You put your game piece on the space labeled initial state. To play the game, you roll a die, and based on the number, you move your piece to a new connected space. And the crucial rule of this machine is that every single time you transition your piece from one space to another, the machine emits one single terminal word. So I move a space. The machine says they. I move another space. It says dog. I keep moving from space to space, spitting out words one by one, moving strictly in a linear progression from left to right. I have no grand plan. I'm just looking at the space I'm currently standing on, rolling the die and moving to the next one until I finally land on the final state space and the sentence ends. That is exactly how a Markov source operates. It generates sentences from left to right and its next move is based only on its current state. It has absolutely no memory of the larger structure it is building. It cannot look back at the beginning of the sentence and it cannot plan for the end of the sentence. It is just a blind chain of transitions. This is essentially how early predictive text on cell phones worked, right? You type, I am going to the, and the phone looks at the current state.
Run some probabilities and suggest store as the next transition. Yes. It is a highly efficient, probabilistic left -right generator. So the million -dollar quotient for cognitive science, can a Markov source, this simple board game, generate human language? To prove definitively that it cannot, Chomsky introduces definition seven, self -embedding. How does the math define a self -embedded structure? A grammar is self -embedding if it contains a non -terminal symbol, let's call it A, that can eventually rewrite into a string of symbols that contains A again. But crucially, that new A must be surrounded by other symbols on both sides. So A eventually drives a string like phi, A, piece AI. It's a cycle.
You start with the concept of A, do a bunch of operations, and you end up with a new A buried right in the middle of the string. It's like a Russian nesting doll. You open the big doll, and inside is a smaller, identical doll, completely surrounded by the outer shell. A nesting doll, or the layers of an onion. Now, in theorem 7, Chomsky proves there are type 2 languages that utilize this nesting doll structure that absolutely cannot be generated by a type 3 Markov source. He uses an example from his earlier work, the mirror image language, which he calls L2. The mirror language. Explain the rules of this specific language. The rule is simple. but structural demanding. Every valid sentence in this language must consist of a string of symbols, which we'll call X, followed immediately by a second string, Y. But Y must be the exact mirror image, the reverse of X. So if my X string is the sequence apple, banana, orange, then my I string must immediately follow it as orange, banana, apple.
The sentence folds in on itself. To generate this mirror language, a machine absolutely requires a self -embedding type 2 grammar. because the machine has to build the sentence from the outside in. It generates the first word, apple, and the last word, apple, simultaneously. Then it steps inward, generating the second word and the second to last word simultaneously. It embeds the structure inside itself. To properly close the sentence on the right side, the machine is forced to remember the exact sequence of the layers it opened on the left side. And here's the fatal blow for the Markov source. A finite state machine produces sentences linearly from left to right. It generates apple, then transitions to a new state and generates banana, then transitions to a new state and generates orange. It's just walking its game piece across the board. But by the time it reaches the middle of the sentence and needs to start generating the mirror image, it is standing on a new square.
It has completely forgotten the path it took to get there. It has no center embedded memory. Wow. It cannot look back to match the left side to the right side. It is physically impossible for a pure left to right machine to build a nested mirror structure. Now, I know some mathematicians and engineers at the time were resistant to this. They loved finite state machines because they were easy to program. They argued, well, what if we just give the board game a memory upgrade? What if we give the finite state machine a little counter chip so it can tally up its moves? Chomsky anticipated that exact counter argument. He references a brilliant paper by a mathematician named Schutzenberger who tested exactly this hypothesis. Theorem 8 in Chomsky's paper states that even if you artificially extend the power of a finite automaton by equipping it with a finite number of infinite counters, it still fails. It still cannot generate the mirror language L2. So throwing more RAM at a Markov chain doesn't fix the fundamental architectural flaw. A left -to -right architecture is simply incompatible with nested, center -embedded structures.
Period. And this brings us to the profound linguistic and cognitive conclusion of this entire section. Chomsky points out that natural English has the essential structural properties of this mere language L2. We use nested, self -embedded dependencies all the time in casual conversation. Give me an example of how we nest dolls in English. Think of a sentence with embedded relative clauses. The rat that the cat that the dog chased bit ate the cheese. The rat that the cat that the dog chased bit ate the cheese. Yeah, my brain has to open a file for the rat, pause that file to open a file for the cat, pause the cat to resolve what the dog did, and then close the files one by one in reverse order to figure out who ate the cheese. We open a thought, we embed a subthought inside it, we close the subthought, and then we close the main thought. Because human language requires this center embedded memory to resolve clauses, human language cannot possibly be generated by a finite state Markov source.
This is such a massive philosophical realization. It proves that humans do not just probabilistically emit words left to right like. basic algorithm predicting the next token. No, we don't. When you speak, you aren't blindly stepping to the next word based on the last word. You are conceptualizing and planning nested hierarchical structures in your head before your vocal cords even start vibrating. The mathematics prove that human cognition operates at least at the complexity of a type two grammar. We are not simple, linear, finite automata. It is a mathematically rigorous proof of the depth of human cognitive complexity, which leads us finally. To the grand finale of the paper, the most mathematically intense, conceptually brutal section of the text. The gauntlet. Because Chomsky is a rigorous scientist. He is not satisfied just waving his hands and saying type two is more powerful than type three because of nesting.
He wants to isolate the exact pure mathematical power source of that difference. Right. We know type two can do things. Type three can't. But what is the exact mechanism? And Chomsky states it bluntly in Theorem 11. If a language is a type 2 language, it is not a type 3 language if and only if all of its grammars are self -embedding. Think about the weight of that claim. He's saying that the sole reason phrased structure trees are more powerful than a linear board game is self -embedding. If you take a type 2 grammar and artificially forbid it from ever using a self -embedding cycle, that complex tree grammar instantly collapses and becomes mathematically identical. to a Type 3 finite state machine.
Wait, let me make sure I'm wrapping my head around this. If I made a personal rule for myself today that I would never, ever speak a self -embedded sentence. Well, hypothetically. Yeah, hypothetically. If I promised to never put a clause inside another clause, are you saying a simple, rigid, left -to -right, predictive text algorithm could perfectly replicate my entire language capability? Yes. That is exactly what theorem 11 proves. Without nesting, your language is just a Markov chain. That is staggering. But how on earth does Chomsky actually prove that? How do you mathematically prove that a grammar without self -embedding is just a finite state machine in disguise? He proves it through an exhaustive mathematical construction. Chomsky says to the reader, give me any regular non -self -embedding type 2 grammar.
Let's call it grammar G. He then proceeds over the course of several pages to manually build a massive, incredibly complex type three grammar, which he names G prime. And his goal is to prove that G prime generates the exact same language as G. So he is going to build a finite state machine that perfectly mimics the tree machine. How does he build G prime? He has to create a dizzying array of new, highly complex, non -terminal symbols. The original tree grammar G year symbols were simple A, B, C. In this new flat grammar G', the non -terminal symbols look like a mathematical nightmare. How so? They are written as a left bracket, followed by B1, dot, dot, dot, BN, a right bracket, and a subscript I. Bracket B, 1 through BN, close bracket, subscript I. That is completely unreadable. What does a bracketed list with a subscript even represent to the machine?
It represents a specific pathway navigated through the parting tree. Let's visualize why this is necessary. A type 2 grammar generates a two -dimensional tree. branching downward and outward. A type 3 grammar is just a one -dimensional flat line of transitions from one state to the next. Chomsky's bracketed symbols are a mathematical trick for flattening a 2D tree into a 1D line. How do you flatten a branching tree without losing information? I need an analogy here. Let's imagine the original type 2 tree is a massive branching underground cave system, and the derivation process is a hiker. exploring this cave. Every time the cave forks, the hiker goes down a level. Okay, I'm the hiker. I start at the entrance, S, and the cave immediately branches left and right. Now, because we established that the original Grammar G is strictly non -self -embedding, we know a crucial geographical fact about this cave. There are no infinite loops. A tunnel will never curve around and feed back into itself. Because there are no loops, the depth of this cave system is strictly finite. It must eventually hit a rock -bottom dead end. The sentences can't nest forever, so the tree has to hit terminal words eventually.
Exactly. And because the depth is finite, there's a strictly finite number of possible paths the hiker can take from the entrance down to the bottom. Chomsky's terrifying bracketed symbols, the bracket B1 through Bn, are basically the hiker's notebook. Oh, I see. It is a running log of the exact path the hiker took to get to their current location. B1 is the first fork they took, B2 is the second fork, B3 is the third fork, and so on. So instead of drawing a map of the entire cave, the new flat machine just keeps a running list of left and right turns in its state name. It remembers where it is.
What about the little subscript I at the end of the bracket? The subscript is the hiker's directional heading. It is either a 1 or a 2. A subscript of 1 means the hiker is currently traveling downward, deeper into the cave along the left wall. A subscript of 2 means the hiker has hit the bottom, turned around, and is currently traveling back upward to find... the next unexplored branch. That is brilliant. The state name itself is a set of GPS coordinates for navigating the tree. So how do the rewriting rules work in this flattened system? Chomsky lists four rules for building G prime. Let's look at the first two to see the hiker in action. Rule 1 says, if BN rewrites as A in the original grammar, then bracket B1 through BN subscript 1 rewrites as A, followed by bracket B1 through BN subscript 2. Okay, let's translate that to the cave. This rule says, if the hiker is traveling downward, meaning subscript 1, and hits a dead end that emits the terminal word A, the hiker drops the word A on the ground.
Correct. Then, the hiker updates their notebook by changing their subscript from a 1 to a 2. They have finished the leftward descent and are turning around to head back up. Exactly. Now, rule 2. If BN rewrites as CD, then bracket B1 through BN subscript 1 rewrites as bracket B1 through BNC subscript 1. This means if the hiker is traveling downward and hits a fork that splits into a left tunnel C and a right tunnel D, the hiker always takes the left tunnel first. They add C to their notebook to record the turn, keep their subscript as a 1 because they're still going down, and keep walking. By meticulously mapping every single possible physical movement in the cave into these flat bracketed state transitions, Chonsky creates G prime. This new grammar just moves from one notebook state to another, dropping terminal words along the way in a straight line, operating exactly like a Markov board game. Yes.
But to prove theorem 11, it is not enough to just build the machine. Chomsky has to mathematically guarantee that this monster G prime actually works. He has to prove it generates every valid sentence the tree would generate and never accidentally regenerates a garbage sentence. And that is what lemmas 3 through 10 are doing. It is a grueling, relentless induction proof. It takes up pages and pages of dense algebra. He is using simultaneous induction on the length of the strings then. Without reading the textbook math to you, the listener, how does induction actually prove this works? Think of mathematical induction like knocking over an infinitely long line of dominoes. Chomsky doesn't try to prove the machine works for every possible infinite length of sentence all at once.
That's impossible. Instead, he first proves that his flat machine works perfectly for a tiny, microscopic sentence. That's knocking over the first domino. Okay. The baseline is established. Then he proves a mechanism. He says, assume the machine works perfectly for a sentence of length tack. I can mathematically guarantee that adding one more word moving to length tack plus one will not break the machine. That is proving that if any one domino falls, it is guaranteed to knock over the next one in line. And because he proved the first domino falls. and he proved the mechanism linking them, he mathematically guarantees that the dominoes will fall forever.
The machine will hold up no matter how long the sentence gets. Exactly. Throughout this domino chain of proofs, he constantly relies on our starting premise to kill off impossible errors. For example, in Lemma 6, he writes out a hypothetical scenario where the flat machine accidentally generates an invalid derivation. But then he looks at the math and says, wait for this error to happen. Symbol BM would have had to loop back around and embed itself. But we explicitly stated at the very beginning that this cave has no loops. It is non -self -embedding. Exactly. Since the loop is geometrically impossible, the hypothetical error is mathematically impossible. The contradiction proves that the flat construction holds firm.
He builds this up step by step. Lemma 8 proves the transitions work for branching nodes. Lemma 10 proves you can take any 2D tree and break it down into a sequence of flat 1D transitions. And then we hit Lemma 12, which spans two full pages of agonizing subscripts. What is the conceptual takeaway of Lemma 12? Lemma 12 proves the reverse operation. It guarantees that if you have a sequence of flat transitions in your new GPRIME machine, you can perfectly reinflate it back into a valid 2D tree in the original grammar. He mathematically guarantees that the flattening process is completely lossless. No structural information is destroyed when you squish the tree into a line. Which leads to the final triumphant strike, theorem 10. If G prime is formed from G by the construction, then there is a derivation of Z in G if and only if there is a derivation of Z in G prime. The two grammars, despite looking completely different, are functionally... perfectly equivalent and since g prime was explicitly built using only rules that go from left to right and which are the defining rules of a type 3 finite state grammar then any non -self -embedding type 2 grammar can be perfectly losslessly simulated by a simple type 3 markov source exactly the only thing a markov source cannot simulate is a self -embedding loop therefore theorem 11 stands absolute the sole source of excess generative power of phrase structure grammars over finite state machines is self -embedding it is like a biologist sifting through millions of lines of DNA and isolating the exact single gene that separates two different species. Chomsky dug through the chaos of unrestricted Turing machines, navigated the tangled lying trees of context -sensitive rules, built impossible hypothetical languages, and squished 2D structures into 1D lines, all to isolate this one, pure mathematical property. Self -embedding. The ability to pause a thought, open a new thought inside it, and return to the original thought. That geometric loop is the spark that makes human language possible. And it is the strict mathematical boundary that simple finite automata cannot cross.
It is a profound realization. By translating language into pure algebra, Chomsky didn't just classify different types of grammars. He mapped the absolute boundaries of computational power itself and placed human cognition squarely on the map. It is a staggering achievement. To summarize this incredible journey for you, we started by looking at language not as a cultural quirk, but as a mathematical function enumerating an infinite set. We learned that simply generating the right words isn't enough. We need a structural description, a blueprint, to actually understand the sentence. We traversed the Chomsky hierarchy from the unrestricted black box chaos of type 0 down through the ranks. We rejected the power of type 1 because its context -sensitive permutations tangled our parsing trees and lied to us about what words were. And finally... Through a grueling, brilliant mathematical construction, we prove that the magic of type 2 and the magic of natural human language lies entirely in the power of the nesting doll. Self -embedding. A rigorous, exhaustive, and ultimately beautiful framework that changed cognitive science forever. But as we wrap up this deep dive, I want to leave you, the listener, with a final, slightly provocative thought to mull over. Because Chomsky, ever the relentless scientist, ends this monumental paper with a cliffhanger he really does he notes that while we have neatly categorized these mathematical types it doesn't actually appear easy to arrive at a perfect structural characterization for natural languages that are type 2 but beyond type 3. But more importantly, he hints and he goes on to prove in his subsequent work that even the beautiful self -embedding type two phrase structure grammars aren't enough to capture a full natural language like English. He realized they are still too rigid to easily handle the complex, elegant, sometimes paradoxical ways we naturally speak. He argues that to truly capture human language, we require an entirely different, even more powerful device sitting on top of the phrase structure, something he calls. transformational grammars. Operations that can take an entire massive parsing tree pick it up and mathematically transform it into an entirely new tree maintaining the underlying meaning while radically changing the surface structure of the sentence. It adds an entirely new dimension of computational complexity to the model. So ask yourself this. If human language fundamentally requires a computational device even more complex than the nested self -embedding phrase structures we just spent an hour mathematically dissecting, what does that say about the sheer staggering computational horsepower hidden inside your own brain every single time you casually open your mouth to order a cup of coffee? It suggests that the machinery of the human mind is far more intricate. more mathematically sublime than we ever could have imagined before this paper was published. Remember where we started? Comparing the organic messiness of biology to the cold rigidity of a mathematical machine. Well, Chomsky built the X -ray machine.
He pointed it at our messy, chaotic language, and he showed us the bones. And it turns out the skeleton of human thought is made of pure mathematics. Thank you for joining us on this incredibly dense, mathematically rigorous deep dive into the formal properties of grammars. Keep exploring the structures hidden in plain sight.