Language for AI Agents: Grammar, Translation, and Speech

This builds on Natural Language for AI Agents, which treated language as a source of information — n-gram language models and the information-seeking tasks built on them: classification, retrieval, and extraction. Those models read text as a sequence of symbols and asked what it was about. Here we turn to how words are arranged: the grammatical structure of language, and the parsing, translation, and transcription tasks that depend on it.

Phrase-structure grammars

The n-gram models above see only a local window; they cannot capture that black dog is well-formed while dog black is odd in English, because that fact is about structure, not adjacency. A grammar generalizes over structure by grouping words into lexical categories (part of speech — noun, verb) and categories into syntactic categories like noun phrase (NP) and verb phrase (VP), then into trees.¹

A context-free grammar (CFG) is a set of rewrite rules, each with a single non-terminal on the left. A probabilistic context-free grammar (PCFG) attaches a probability to each rule, so the grammar assigns a probability to every string. A rule looks like

reading: a verb phrase is a bare verb with probability 0.70, or a $VP$ followed by an $NP$ with probability 0.30. AIMA builds a tiny grammar ${\mathcal{E}}_0$ for a fragment of English, with a lexicon grouping words into categories and rules combining them.

The output of parsing a sentence is a parse tree: nested phrases, each labeled with its category, whose probability is the product of the rule probabilities used.

Any grammar over a small hand-written rule set will both overgenerate (accept nonsense like Me go Boston) and undergenerate (reject valid sentences). The generative power of a grammar formalism is classified by the Chomsky hierarchy, which sorts grammars by the form of their rewrite rules into four nested classes, each strictly containing the one below:

• Regular grammars allow rules with a single nonterminal on the left and a terminal optionally followed by one nonterminal on the right ($X\to aY$). They are exactly as powerful as finite-state machines. They can express $a^{\ast }{b}^{\ast }$ but not the balanced-parenthesis language $a^n{b}^n$ — counting requires memory a finite automaton does not have.
• Context-free grammars (CFGs) allow any single nonterminal on the left, rewritten in any context ($X\to \gamma$). They add exactly the counting regular grammars lack: $a^n{b}^n$ is context-free, but $a^n{b}^n{c}^n$ — matching three counts at once — is not.
• Context-sensitive grammars require only that the right side be at least as long as the left ($\alpha X\beta \to \alpha \gamma \beta$, so $X$ becomes $\gamma$ only in the context of $\alpha$ and $\beta$). They can express $a^n{b}^n{c}^n$.
• Recursively enumerable (unrestricted) grammars place no constraint on the rules and are Turing-equivalent.

The containments are proper: each class recognizes strictly more languages than the one below it, but at a cost — the higher up the hierarchy, the less efficient the parsing algorithms. CFGs are the usual choice for natural and programming languages, sitting at the sweet spot where cubic-time parsing (the next section) is still possible, though some natural-language constructions (cross-serial dependencies in Swiss German, for instance) are known to exceed context-free power.

Syntactic analysis (parsing)

Parsing recovers the phrase structure of a string according to a grammar.² One could search top-down (start from $S$, expand toward the words) or bottom-up (start from the words, build up to $S$), but both repeat work: a substring analyzed inside one branch of the search is re-analyzed in another. The fix is dynamic programming — analyze each substring once, store the result in a table called a chart, and reuse it. Parsers that do this are chart parsers.

The CYK algorithm is a bottom-up chart parser. It requires the grammar in Chomsky Normal Form — every rule is either $X\to \text{word}$ or $X\to YZ$ — into which any CFG can be converted. CYK fills a table $P[X,\text{start},\text{length}]$ holding the probability of the most probable constituent of category $X$, of that length, starting at that position; it works from short spans to long ones, combining two adjacent subspans by every binary rule.

CYK uses $O(n^{2}m)$ space and $O(n^{3}m)$ time for $n$ words and $m$ nonterminals, commonly written $O(n^3)$ since $m$ is fixed. Its virtue on ambiguous sentences is that it never enumerates the parse trees — a sentence like Fall leaves fall and spring leaves spring can have exponentially many parses, yet CYK computes the probability of the most probable tree in cubic time by storing shared subtrees once in the chart.

Filling the chart cell by cell

Run the numbers on the wumpus is dead with a tiny CNF grammar. The lexical rules (each $X\to \text{word}[p]$) and the binary rules (each $X\to YZ[p]$):

CYK indexes each cell by (start, length). Length-1 cells come straight from the lexicon. Then it builds length-2 spans, and finally the length-4 span, each time splitting the span every possible way and applying every binary rule. The filled chart, with the one nonzero entry in each occupied cell:

The length-2 cell at start $1$ combines $\text{Art}$ (start $1$, len $1$) with $\text{Noun}$ (start $2$, len $1$) under $NP\to \text{Art}\text{Noun}$: $P=1.0\times 1.0\times 0.6=0.6$. The length-2 cell at start $3$ combines $\text{Verb}$ and $\text{Adj}$ under $VP$: $P=1.0\times 1.0\times 0.5=0.5$. The middle spans (start $2$ len $2$; any len $3$) stay empty because no rule combines $\text{Noun}\text{Verb}$ or the length-3 pieces. The top cell (start $1$, len $4$) has only one productive split, len1 $=2$ (the $NP$) plus len2 $=2$ (the $VP$), under $S\to NPVP$:

Reading the back-pointers down from that top cell recovers the parse $[S[NP[\text{Art}\text{the}][\text{Noun}\text{wumpus}]][VP[\text{Verb}\text{is}][\text{Adj}\text{dead}]]]$ with probability $0.27$. The other split of the length-4 span (len1 $=1$: just $\text{Art}$, plus len2 $=3$: empty) contributes nothing, which is why the $\max$ in the algorithm leaves $0.27$ standing.

A PCFG's rule probabilities are learned by counting over a treebank — a corpus of hand-parsed sentences, the Penn Treebank being the best known — or, harder, from unparsed text with the inside-outside algorithm, the parsing analogue of the forward-backward EM procedure for HMMs. The modern, neural version of this task is the NLP subject's constituency parsing lesson.

Augmented grammars and semantic interpretation

Plain CFGs are too blunt: they cannot express that I smell is grammatical but I smells is not (subject-verb agreement), nor that eat a banana is more probable than eat a bandanna (a lexical dependency). An augmented grammar attaches variables to categories.³ Writing $NP(c,pn,head)$ threads a case $c$, a person-number $pn$, and a head word through the rule, so a single rule enforces agreement that would otherwise need an exponential blowup of subscripted categories:

Read right-to-left: an $NP$ and a $VP$ form an $S$ only when the $NP$ is in the subjective case and its person-number $pn$ matches the verb's. When these rules are translated into logic they become a definite clause grammar (DCG), which lets parsing be done by logical inference.

The same augmentation carries semantics. Under compositional semantics, the meaning of a phrase is a function of the meanings of its parts. Attach a semantic variable to each category, and each rule says how to combine the parts' meanings. For arithmetic, $Exp(x)\to Exp(x_1)Operator(op)Exp(x_2)\{x=Apply(op,x_1,x_2)\}$ builds the value of an expression from its subexpressions. For English, John loves Mary is built by giving the $VP$ loves Mary the $\lambda$-expression $\lambda xLoves(x,\text{Mary})$ and applying it to the subject's meaning.

Full English adds pragmatics (resolving indexicals like I and today against the situation, and reading the speech act — is the utterance a statement, a question, a command?), quantification scope, long-distance dependencies, and figures of speech like metonymy (Chrysler announced ...) and metaphor. Disambiguation — choosing the intended reading — needs four models working together: a world model (what is likely true), a mental model (what the speaker intends), a language model (what strings are likely), and, for speech, an acoustic model. The last two are precisely the pieces the next two sections need.

Machine translation

Machine translation (MT) converts text from a source language into a target language.⁴ It is hard because languages carve up the world differently (French doux spans English soft, sweet, and gentle), and a faithful rendering may require understanding the situation, not just the words. Classical systems span a range shown by the Vauquois triangle (Vauquois, 1968): a shallow transfer model maps source structures directly to target structures, while a deep interlingua system parses all the way to a language-independent meaning and generates from there.

The triangle organizes every classical MT design by how deep it analyzes before it crosses to the target. Its left side is analysis: starting from the source words at the bottom-left corner, a system climbs through source syntax to source semantics, and at the apex to an interlingua — a representation stripped of any particular language, meaning alone. Its right side is generation, the mirror descent from a target-side representation back down through target syntax to target words. A translation is a path up the left side, across at some level, and down the right. The crossing level names the approach:

• Direct translation crosses at the very bottom: substitute words (and reorder a little) with no structural analysis at all. Cheap, and adequate only for close languages.
• Transfer climbs partway — to syntax or shallow semantics — applies a set of bilingual transfer rules that rewrite a source structure into the corresponding target structure, then generates. It needs a separate rule set for each language pair and each direction.
• Interlingua climbs to the apex, parsing the source into language-independent meaning, then generates the target from that meaning alone. It needs only an analyzer and a generator per language — $2n$ components for $n$ languages, against the $n(n-1)$ transfer systems every pair would otherwise require — but reaching a clean, fully language-neutral interlingua is hard.

The most successful classical approach is statistical MT, which learns from a bilingual corpus of parallel texts and needs no hand-built grammar or ontology. Cast as a noisy-channel problem, translating English $e$ into French $f$ finds

The second equality is worth deriving, since the same step reappears in spam, speech, and spelling correction. Bayes' rule expands the quantity we actually want, $P(f\mid e)$, into

The denominator $P(e)$ is the probability of the English sentence we were handed. It does not depend on the candidate French $f$, so as $f$ ranges over all translations it is a fixed positive constant, and dividing every candidate's score by the same constant cannot change which candidate is largest. Dropping it,

Here $P(f)$ is the target language model (how good is this French sentence?) and $P(e\mid f)$ the translation model (how well does it correspond to the English?). The benefit is a decomposition: instead of learning the one hard distribution $P(f\mid e)$ directly, we learn a fluency model $P(f)$ from monolingual French — of which there is far more — and a faithfulness model $P(e\mid f)$ from the scarcer parallel corpus, and let Bayes' rule recombine them. This is the noisy-channel shape: a source $f$ is imagined to pass through a channel that garbles it into the observed $e$, and decoding inverts the channel.

The language model $P(f)$ is a French n-gram model; the translation model is learned from the parallel corpus by aligning phrases and modeling their reordering with a distortion $d_i$, the shift each French phrase makes relative to its predecessor. The full model factors as

Reading off the distortions. The distortion is not the crossing-arrow picture's how far did this phrase move in the loose sense; it is defined precisely by where each French phrase's words sit. Number the French words left to right and set

where $\mathrm{START}(f_i)$ is the position of the first word of the $i$-th English phrase's translation in the French output, and $\mathrm{END}(f_{i-1})$ the position of the last word of the previous phrase's translation. A phrase that lands immediately after its predecessor gets $d=0$. Take the ordering in the figure, where the English phrases $e_1{e}_2{e}_3{e}_4$ are realized in French as $f_1$ (positions 1–4, Il y a un), then $f_3$ (wumpus, position 5), then $f_2$ (malodorant, position 6), then $f_4$ (qui dort, positions 7–8):

The point of this definition is arithmetic, not linguistics. A sentence of $n$ phrases has $n!$ possible orderings, an impossible number of parameters to learn, but $d_i$ ranges only over $\{-n,\dots ,+n\}$, so the whole distortion distribution $P(d_i)$ has just $2n+1$ entries. The model does not try to explain why French puts the adjective after the noun — that fact lives in the French language model $P(f)$; the distortion term only summarizes how volatile the reordering tends to be, learned by counting how often each shift $d=0,\pm 1,\pm 2,\dots$ occurs across the aligned corpus.

Because there are astronomically many candidate translations, the best $f$ is found by beam search with a probability heuristic, not exhaustive enumeration. The parameters are learned by aligning sentences and phrases in the corpus and refining with EM. Neural MT — the encoder-decoder and attention models that supplanted this pipeline — is the subject of the NLP machine translation lesson.

Speech recognition

Speech recognition identifies the words a speaker uttered from the acoustic signal.⁵ It is hard because sound is ambiguous: recognize speech and wreck a nice beach sound nearly identical (segmentation — fast speech has no pauses between words), the sounds of adjacent words blur (coarticulation), and homophones like to, too, two sound the same. Like translation, it is a noisy-channel problem. Seeking the most probable word sequence given the sounds,

where $P(\text{sound}\mid \text{word})$ is the acoustic model (how words sound) and $P(\text{word})$ is the language model (which word sequences are likely — ceiling fan beats sealing fan). Claude Shannon named this the noisy channel model: the words are a message sent over a noisy channel and received as sounds.

The acoustic signal is sampled (typically 8 kHz), sliced into ~10 ms frames, and each frame summarized by a feature vector (mel-frequency cepstral coefficients). Words are modeled as sequences of phones — the ~100 basic speech sounds, written in the ARPAbet — and each phone is a small HMM (onset, middle, end) whose self-loops absorb variation in duration. A pronunciation model strings phone HMMs into a word, allowing dialect and coarticulation variants.

With acoustic and language models in hand, the most probable word sequence is decoded with the Viterbi algorithm over the combined HMM.

A two-step Viterbi trace. Viterbi is dynamic programming over the trellis of states and time steps: it keeps, for each state, the probability of the single best path that ends there, and extends it one frame at a time. Take a stripped-down word HMM with two hidden phone states, $A$ and $B$, start probabilities ${\pi }_A=0.6$, ${\pi }_B=0.4$, transition probabilities $P(A\mid A)=0.7$, $P(B\mid A)=0.3$, $P(A\mid B)=0.4$, $P(B\mid B)=0.6$, and observation likelihoods for the two frames $o_1,o_2$ actually heard: $P(o_1\mid A)=0.5$, $P(o_1\mid B)=0.1$, $P(o_2\mid A)=0.2$, $P(o_2\mid B)=0.6$. Write ${\delta }_t(s)$ for the best-path probability into state $s$ at time $t$.

Step 1 (initialize on $o_1$): ${\delta }_1(A)={\pi }_{A}P(o_1\mid A)=0.6\cdot 0.5=0.30$ and ${\delta }_1(B)={\pi }_{B}P(o_1\mid B)=0.4\cdot 0.1=0.04$.

Step 2 (recurse on $o_2$): for each state, take the better of the two incoming paths, then multiply by that state's emission of $o_2$.

The best final state is $B$ ($0.054>0.042$), and its back-pointer names $A$ as the winning predecessor, so the decoded state path is $A\to B$. Both winning transitions came from $A$ at time 1, which is why Viterbi stores one back-pointer per state rather than enumerating all $2^2$ paths — and over a real utterance of hundreds of frames, that is the difference between linear and exponential work.

Parameters are learned by EM from a corpus of speech paired with transcripts, replacing the laborious hand-labeling of spectrograms used in early systems. Accuracy depends on vocabulary size — word error rate is below 0.5% for the 11 digit words but rises to ~20% on a 64,000-word corpus — and on microphone quality and task constraint. The modern end-to-end neural approach is the NLP subject's automatic speech recognition lesson.

From n-grams to transformers

Everything above predates the deep-learning turn, and AIMA's 3rd edition (2009) catches the classical account just before it was overtaken. What replaced the n-gram table and the HMM kept the problems — the argmax over word sequences, the encoder/decoder split, the noisy channel — and changed the representation of the distributions inside them. Tracing the replacement clarifies which parts of this lesson are permanent and which were artifacts of counting.

The bottleneck the classical models shared. An n-gram model represents a word as an atomic symbol, so cat and kitten are as unrelated as cat and Tuesday: the model has no notion that some words are close in meaning. And a trigram sees only two words of context; the count table for a five-word window over a $10^5$-word vocabulary would need $10^{25}$ entries, so the Markov horizon is short by necessity, not choice. Both limits are about representation. The neural line of work attacked exactly these two.

Distributed word embeddings (2013). Mikolov et al. (Efficient Estimation of Word Representations in Vector Space, 2013) trained shallow networks — skip-gram and CBOW, together called word2vec — to predict a word from its neighbors, and read off the hidden layer as a dense vector for each word. Words used in similar contexts landed near each other in the vector space, so cat and kitten became close, and the vectors even supported analogies by arithmetic (the widely reported $\text{king}-\text{man}+\text{woman}\approx \text{queen}$ regularity). This dissolved the atomic-symbol problem: a word was now a point in a continuous space where similarity is a distance.

Sequence-to-sequence and attention (2014–2015). Sutskever, Vinyals & Le (Sequence to Sequence Learning with Neural Networks, NeurIPS 2014) built a translator from two recurrent networks — an encoder that reads the source sentence into a fixed-length vector, and a decoder that unrolls that vector into the target sentence. This is the same encoder/decoder division AIMA describes for statistical MT, now with learned recurrent states instead of phrase tables and distortion counts. The fixed-length vector was the weak point: a long sentence had to be crushed into one vector. Bahdanau, Cho & Bengio (Neural Machine Translation by Jointly Learning to Align and Translate, ICLR 2015) added attention — at each output step the decoder computes a weighted average over all encoder states, learning where to look. Attention is a learned, soft version of the alignment that phrase-based MT computed by counting, and it lifted the fixed-window limit.

The transformer (2017). Vaswani et al. (Attention Is All You Need, NeurIPS 2017) removed the recurrence entirely and kept only the attention. In self-attention, every position attends to every other position in the sequence in one parallel operation, so the effective context is the whole sentence rather than a fixed $n-1$ window, and there is no left-to-right recurrence to serialize — the whole sequence is processed at once. This is the sharpest break with the n-gram picture: where a trigram conditions on the two preceding symbols, a transformer layer conditions on every symbol, with learned weights deciding which ones matter.

Pretraining at scale (2019–2020). With the architecture fixed, the last shift was in how it was trained. Devlin et al. (BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding, NAACL 2019) pretrained a transformer on a masked-language-modeling objective — hide some words and predict them from both sides — producing representations that, fine-tuned, set new results across many language tasks. Where the n-gram language model is strictly left-to-right, BERT is bidirectional, conditioning each prediction on the full surrounding context. Brown et al. (Language Models are Few-Shot Learners, NeurIPS 2020) scaled a left-to-right transformer to 175 billion parameters as GPT-3 and showed that at that scale the model performs new tasks from a few examples given in the prompt, with no gradient updates — in-context few-shot learning. These are results about what a large pretrained language model can do; they do not change the underlying object, which is still a distribution over word sequences.

What survived. The through-line is that the shape of every task in this lesson carried over intact. A GPT-style model still scores text as an argmax over $P({\text{word}}_{1:n})$ — the same quantity the trigram estimated, now factored left-to-right as ${\prod }_{i}P(w_i\mid w_{1:i-1})$ with the full history instead of a two-word window. Neural translation still splits an encoder that reads the source from a decoder that generates the target, exactly the division of statistical MT. Classification is still ${\mathrm{argmax}}_{c}P(c\mid \text{text})$. What changed is what fills the probabilities: learned continuous representations in place of count tables, and attention over the whole sequence in place of a fixed Markov horizon. The classical models named the problems cleanly, which is why they remain worth knowing; the neural models solved them better by fixing the representation. The full modern treatment — embeddings, transformers, pretraining, and the tasks rebuilt on them — is the sibling natural language processing subject.

Where this sits

Two patterns run through the whole chapter. The first is the noisy-channel model: classification, translation, and speech recognition all reduce to $\mathrm{argmax}P(\text{observation}\mid \text{source})P(\text{source})$, a likelihood times a prior recovered by Bayes' rule — the same shape as diagnosis with probability. The second is the split between statistics and structure: n-gram and HMM models win on translation and speech precisely because large corpora exist for those tasks, while structured parsing lags because parsed corpora are scarce and parsing is rarely an end in itself.

Both patterns survived the deep-learning transition even as the models underneath were replaced: a transformer language model is still an $\mathrm{argmax}$ over $P(\text{word sequence})$, and neural translation still separates an encoder that reads the source from a decoder that models the target. That is the throughline to the natural language processing subject — same problems, sharper tools. Language is the interface between an agent and the knowledge and people it must work with, which is why it closes the loop from perception through reasoning to decision-making.