How do Computers Learn Sentence Structure? (Context-Free Grammars)

Before diving into grammar, we need to talk about syntax. The set of rules that governs how we arrange words in sentences.

Now, syntax is not the same as morphology. Morphology is about what happens inside a single word, in its root, prefixes, suffixes, and how it’s built. Syntax, on the other hand, is about how words come together; how we go from “run” to “She runs every morning” without our brain throwing an error.

And here’s something that might surprise you: syntax is not even about meaning. A sentence like “Colorless green ideas sleep furiously” is grammatically perfect, but semantically, it makes no sense. And yet, that’s the magic.

Syntax is about structure, not sense.

If you can’t access the full article, visit here: https://sandanisesanika.medium.com/how-do-computers-learn-sentence-structure-context-free-grammars-c653e3fe8b7e?sk=21e35b9e3180e49b6eed711196a42d54

Why Should You Even Care About CFGs?

Let me put it this way: if you’ve ever used a grammar checker, searched something on Google, translated a sentence online, or asked your phone a question, all of that involves syntax. And to handle syntax, machines need a way to “understand” the structure of language.

Enter grammars.

Grammar is like a recipe. It tells the machine how valid sentences can be made. And context-free grammars, or CFGs, are one of the most popular and useful kinds.

But why “context-free”? We’ll get to that. First, let’s understand what CFGs are trying to solve.

Who Did What to Whom?

One of the most fundamental things syntax can help figure out is this: who did what to whom. Take the sentence “Oswald shot Kennedy.” Simple enough. But what about “Kennedy was shot by Oswald”? Same meaning, different structure. Now throw in a sentence like “Oswald, who shot Kennedy, was shot by Ruby,” and things get even messier.

Syntax helps machines analyze these sentence patterns. And even if a parse tree doesn’t directly* say who did what, it sets the stage. It shows how the sentence is built, and that’s a vital first step.

(*A parse tree, also known as a parsing tree or derivation tree, is an ordered, rooted tree that visually represents the syntactic structure of a string (such as a sentence in a natural language or a line of code in a programming language) according to a specific context-free grammar.)

Constituents and the Structure of Sentences

When we look at a sentence, our brain breaks it into chunks. For example, in “The big elephant arrived,” we recognize “The big elephant” as a group; a noun phrase.

These chunks are called constituents ; groups of words that belong together.

In English, we often work with:

• Noun phrases (like “the blue balloon”)
• Verb phrases (like “was walking to the park”)
• Prepositional phrases (like “under the leaking roof”)
• Sentences or clauses (full thoughts)

These pieces nest inside one another, creating a sort of tree, and that’s exactly what CFGs help us build.

So What Is a Context-Free Grammar?

Think of a CFG as a toolkit for building sentences. It has:

1. A list of terminal symbols; the actual words.
2. A list of non-terminal symbols; labels like NP (noun phrase), VP (verb phrase), S (sentence), etc.
3. A start symbol, usually S, which stands for Sentence.
4. A set of production rules; the “rewrite” instructions.

These rules look like this:

S → NP VP
NP → Det Nominal
Nominal → Noun
Det → a | the
Noun → flight | elephant
VP → Verb
Verb → arrived

Using these rules, we can generate a sentence or analyze one. Either way, CFGs help machines understand how words fit together.

And why are they called “context-free”? Because the rules apply regardless of where the symbol appears. If the rule says “NP → Det Nominal,” that rule applies anywhere an NP shows up; it doesn’t care about the context around it.

That’s both a strength and a limitation.

A Quick Derivation Walkthrough

Let’s say we want to generate the sentence: “a flight.”

We start with the symbol NP. The rules tell us:

• NP becomes Det + Nominal
• Det becomes “a”
• Nominal becomes Noun
• Noun becomes “flight”

So we’ve rewritten NP → a flight. This process, called derivation, gives both the sentence and the way in which to draw its parse tree.

Grammar Types: A Peek at the Chomsky Hierarchy

No discussion of CFGs is complete without mentioning Noam Chomsky’s famous hierarchy of grammars:

1. Regular grammars — very simple, used in things like regex.
2. Context-free grammars — what we’re focused on.
3. Context-sensitive grammars — more powerful, but harder to process.
4. Unrestricted grammars — equivalent to Turing* machines.

Most programming languages are designed using context-free grammars, and many aspects of natural language can be described this way; however, with natural language, things can be complicated.

Turing Machine https://upload.wikimedia.org/wikipedia/commons/0/03/Turing_Machine_Model_Davey_2012.jpg

(*At each step, the Turing machine reads the symbol under the head, consults the rules, and performs the actions.)

Recursion and Infinite Possibilities

CFGs are cool because they allow recursion. That means a rule can refer to itself.

Let’s say we define:

NP → NP PP

This allows us to build phrases like:

• “Flights”
• “Flights from Denver”
• “Flights from Denver to Miami”
• “Flights from Denver to Miami in February on a Friday…”

And it can go on forever. Recursion is one of the most powerful features of CFGs!

But CFGs Aren’t Perfect

Real language has quirks. There are cases where CFGs overgenerate (they allow weird, ungrammatical sentences ) or undergenerate (by not allowing things that are fine).

Some problems CFGs run into:

• Agreement: “This dog eats” vs. “These dogs eat” — the verb form changes based on number.
• Subcategorization: Some verbs need objects, some don’t. “John sneezed” is fine. “John sneezed the book” is… weird.
• Movement: In complex questions like “Which flight did you say you booked?”, the structure gets tangled.

These challenges have led to more advanced grammar models, but CFGs remain foundational.

Chomsky Normal Form

https://www.ques10.com/p/64994/define-chomsky-normal-form-simplify-following-cf-1/

To make CFGs easier to process by machines, we sometimes convert them into Chomsky Normal Form (a simplified format where each rule has only two non-terminals or one terminal on the right-hand side). It doesn’t change what the grammar can express, just how it’s written.

Context-free grammars are like the blueprint for building and analyzing sentence structure. They help machines go beyond just recognizing words and begin to see how those words come together into meaning, or at least into form.

They’re not perfect. They can’t handle every twist of natural language. But they’ve laid the groundwork for everything from syntax checkers to chatbots to language models.

So next time you use Google Translate or Grammarly, remember that somewhere in the background, a grammar like this helped the system understand your sentence!!

Reference:

• Dr. Nisansa de Silva’s NLP Lectures