Linear Grammar¶
A context-free grammar whose productions contain at most one nonterminal on each right-hand side, maintaining one active derivational obligation while emitting terminals around it.
Core Idea¶
Linear grammars restrict branching in context-free derivation. Each production replaces a nonterminal with terminal strings surrounding at most one further nonterminal. A derivation therefore carries a single active variable until a terminating production produces an all-terminal word.
Consistently right-linear or left-linear grammars characterize regular languages. General linear grammars may place the surviving variable on either side and can express dependencies such as equal blocks, while remaining strictly less expressive than arbitrary context-free grammars that branch into multiple nonterminals.
Scope of Application¶
- Formal-language classification. Locates languages between regular and context-free families.
- Automata theory. Connects linear languages to one-turn pushdown behavior.
- Parsing complexity. Exploits the absence of nonterminal branching.
- Grammar normalization. Tests whether equivalent presentations preserve linear language membership.
Clarity¶
Count nonterminal occurrences, not merely distinct nonterminal names, on every right side. State whether linear modifies the grammar syntax or the existence of a linear grammar for a language. Inclusion test: Inspect every production and verify that its right side contains no more than one nonterminal; then distinguish arbitrary linear from consistently left- or right-linear form. Exclusion test: Exclude grammars with any production containing two active nonterminals, unrelated uses of linear in grammar notation, and automata descriptions with no grammar translation. Nearest boundary: A regular grammar is consistently left-linear or consistently right-linear; an arbitrary linear grammar may place the lone nonterminal on different sides and generate nonregular languages. Exit condition: The grammar leaves the class as soon as one production right side contains two or more nonterminals.
Manages Complexity¶
The one-active-variable invariant makes derivations easier to analyze while retaining two-sided dependencies beyond finite-state power. It separates branching complexity from string length.
Abstract Reasoning¶
- Declare terminals, nonterminals, start symbol, and productions.
- Count right-side nonterminal occurrences rule by rule.
- Track the lone active nonterminal through derivations.
- Check whether orientation is uniformly left or right.
- Distinguish grammar classification from language classification.
Knowledge Transfer¶
The restriction pattern transfers to weighted or controlled grammars only after their production semantics are restated. Linear algebra uses of linear are unrelated.
Relationships to Other Abstractions¶
Current abstraction Linear Grammar Domain-specific
Parents (1) — more general patterns this builds on
-
Linear Grammar is a kind of Context-Free Grammar Domain-specific
A Linear Grammar is a Context-Free Grammar whose production right-hand sides contain at most one nonterminal.
Hierarchy paths (2) — routes to 2 parentless roots
- Linear Grammar → Context-Free Grammar → Formal System → Formalization → Representation → Abstraction
- Linear Grammar → Context-Free Grammar → Formal System → Formalization → Transformation → Function (Mapping)
Neighborhood in Abstraction Space¶
Linear Grammar sits in a crowded region of the domain-specific corpus (32nd percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.
Family — Logical Connectives & Formal Systems (13 abstractions)
Nearest neighbors
- Literal movement grammar — 0.90
- Chomsky Normal Form — 0.89
- Stochastic Grammar — 0.89
- Smallest grammar problem — 0.88
- Generalized Büchi Automaton — 0.88
Computed from structural-signature embeddings · 2026-10-08