Why does A appear twice in the rule?

One occurrence labels the larger resulting constituent; the other labels its embedded constituent.

Does the recursion have to run forever?

No. A terminating alternative such as A → h ends the derivation.

Are repeated A nodes duplicates to delete?

No. They encode distinct levels in the chosen phrase structure.

AI Glossary / Natural language and speech / Advanced

Chomsky-adjunction

Definition

Chomsky-adjunction, in the context-free grammar sense used here, is a recursive way of extending a constituent while retaining its category. A rule such as A → A B allows another B constituent to be added to an A constituent, producing a larger A. Repeated application supports an arbitrarily long finite sequence of added constituents when suitable terminating rules are available.

What it means

A grammar can describe a phrase followed by one modifier, two modifiers, three modifiers, and so on without listing a separate production for every length. The same recursive pattern reuses the category of the phrase being extended.
For example, a rule VP → VP PP can attach a prepositional phrase to an existing verb phrase and still produce a verb phrase. The result contains an inner VP and an outer VP. It records which phrase contains the added material and how repeated additions nest.

How it works

The rule A → A B contains A on both sides. To produce a finite terminal string, the grammar must also provide a way for that recurring A to terminate and for B to produce its content. Without an appropriate base derivation, recursion alone does not yield a completed phrase.
Each application creates a parent A with an A child and a B child. In this right-addition form, the B appears after the existing A's yield. Further applications add more B material while preserving the earlier subtree.
A parser must recognize the recursive structure using a strategy that handles it appropriately. A naive top-down procedure that repeatedly expands the leftmost A before consuming input can loop. This implementation issue does not mean the grammar has no finite derivations; it means the parsing procedure must accommodate left recursion.

Three practical examples

A grammar designer models successive modifiers of a verb phrase with a recursive production, reducing the need for a list of separately enumerated phrase lengths.
A parser comparison examines whether one grammar produces a flat phrase and another produces nested same-category phrases for the same words. Matching terminal strings does not establish identical structure.
A syntax teaching tool starts with a simple phrase and adds one modifier at a time. It displays the new outer node so students can distinguish the newly attached material from the original constituent.

Think of it this way

Imagine extending a folder by placing the existing folder and one new item inside a larger folder bearing the same category label. Repeating this creates layers. The contents grow, but the old folder remains an identifiable part of the larger structure.

Worked example

Use a grammar with three productions: A → A B, A → h, and B → m. The lowercase symbols h and m are terminal tokens, while A and B are grammatical categories.
With no recursive application, A → h produces the one-token string h. With one application, A → A B → h B → h m produces h m. With two applications to the recurring A, the derivation begins A → A B → A B B, then terminates the inner A as h and both B symbols as m, producing h m m.
The two-addition tree in bracketed notation is (A (A (A h) (B m)) (B m)). Reading its leaves gives h m m. It contains three A nodes, two B nodes, and three terminal leaves. The inner A generates h; each surrounding A adds one B.
After k recursive applications, the completed string is h followed by k copies of m. It has k+1 terminal tokens, k+1 A nodes, and k B nodes. For k=3, those counts are four tokens, four A nodes, and three B nodes. Every individual completed derivation is finite, although no fixed maximum k is imposed by these rules.
Now replace the two-addition structure with a direct production A → h m m. That production generates the same three-token string but yields a flat tree with one A node. The shared word sequence therefore does not make the two analyses structurally identical. Also, adding only a finite list of direct productions would cover only the lengths listed, whereas the recursive grammar covers every nonnegative k.

Illustrative case study

Fictional example: SyntaxBench maintains a small grammar for analyzing equipment descriptions. Its older rules enumerate several modifier lengths. A revision introduces recursive same-category attachment, and a test confirms that the old example sentences still parse.
The reviewers also compare trees and discover that an extraction routine expects all modifiers to be immediate children of a single flat phrase. It misses some modifiers in the new nested trees. The team updates the traversal and checks both accepted strings and recovered structures. The invented case illustrates a compatibility issue; it does not claim that recursion alone improves linguistic accuracy or parser speed.

Common misconceptions and mistakes

Chomsky-adjunction is not synonymous with Chomsky normal form. The former describes the recursive extension pattern discussed here; the latter restricts the shapes of grammar productions. A grammar containing A → A B is not automatically in normal form, because its other productions also matter.
It is also misleading to describe an actual sentence as containing infinitely many modifiers. The grammar permits unbounded finite lengths. Finally, adjunction has other technical uses, including in tree-adjoining grammars. Those formalisms have their own operations and constraints and should not be reduced to this single context-free production pattern.

Business use

This concept is useful when reviewing grammar-based extraction or parsing components that must handle repeated modifiers. Check both language coverage and the tree shape consumed by downstream software. A shorter rule set is not sufficient evidence of improved runtime, and preserving example strings is not sufficient evidence that extraction behavior is preserved. Include cases with zero, one, and several additions.

Check your understanding

Answer: What string results from three additions in the example? h m m m.

How many A nodes does its tree contain?

Answer: Four.

Why is the direct rule A → h m m structurally different?

Answer: It places the three terminals under one A rather than preserving the nested A-and-B structure.

Related terms

Context-free grammar
Binary branching
Chomsky normal form
recursion
left recursion
constituent
adjunct
tree-adjoining grammar

Learn next

Draw the trees for zero through three additions and verify their terminal order. Then compare recursive and flat analyses, and study how chart-based parsing can handle left-recursive grammars without a naive expansion loop.

Sources

Jurafsky and Martin, Speech and Language Processing, chapter 19, section 19.4, recursive grammar rules and Chomsky-adjunction: https://web.stanford.edu/~jurafsky/slp3/19.pdf

Previous: Choice set Next: Chomsky normal form