Skip to content

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.

Version
v1 · 2026-09-28 · History
Domain-specific #
10415
Domain group
Applied Sciences & Engineering
Origin domain
Computer Science & Software Engineering
Subdomains
Formal Languages, Grammar Classes, Automata Theory → Computer Science & Software Engineering
Aliases
Linear context-free grammar

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.

Structural Signature

Sig role-phrases:

  • Terminal alphabet — Supplies emitted symbols of generated strings. It is required vocabulary. Counterfactual: Without terminals the grammar cannot define its string language.
  • Nonterminal set and start symbol — Represent the single evolving derivational obligation. It is required control. Counterfactual: A production system without designated start and variables is not the grammar formalism.
  • Linear production restriction — Limits each right side to zero or one nonterminal. It is defining constraint. Counterfactual: Two nonterminals on one right side make the grammar nonlinear context-free.
  • Left terminal context — Accumulates terminals before the remaining nonterminal. It is derivation output. Counterfactual: Restricting all growth to one side yields a regular subclass.
  • Right terminal context — Accumulates terminals after the remaining nonterminal. It is derivation output. Counterfactual: Using both sides across productions enables nonregular linear languages.
  • Termination production — Removes the final nonterminal and completes a terminal word. It is completion rule. Counterfactual: Without a terminating route no finite word is generated.

What It Is Not

  • It is not any grammar written in a linear sequence.
  • It is not equivalent to regular grammar.
  • It is not a property of one derivation only; every production must satisfy the restriction.
  • A language can be linear even if one presented grammar for it is not.
  • Closest near-miss. 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.

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.

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

  1. Declare terminals, nonterminals, start symbol, and productions.
  2. Count right-side nonterminal occurrences rule by rule.
  3. Track the lone active nonterminal through derivations.
  4. Check whether orientation is uniformly left or right.
  5. 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.

Examples

Canonical

The rules S→aSb and S→ε maintain one S while adding matched terminal symbols on both sides, generating aⁿbⁿ, a linear but nonregular language.

Mapped back: active nonterminal → one S; left output → a; right output → b; termination → epsilon.

Applied / In Practice

A Dyck-style rule S→SS contains two nonterminals on the right and therefore violates linearity even if other productions contain only one.

Mapped back: production → S to SS; nonterminal count → two; verdict → nonlinear context-free.

Structural Tensions

T1 — Single Active Obligation versus Two-Sided Output. Only one nonterminal persists, yet terminals can accumulate on both sides and enforce distant dependencies.

Diagnostic: Does the rule maintain one active variable while coordinating both ends?

T2 — Syntactic Restriction versus Language Property. A language is linear if some linear grammar generates it, even when a given grammar for it is nonlinear.

Diagnostic: Is the claim about this grammar or existence of an equivalent grammar?

Structural–Framed Character

Linear Grammar is strongly structural.

Structural Core vs. Domain Accent

The skeleton is one active recursive placeholder. Formal-language theory supplies productions, derivations, language classes, and pushdown recognition.

This entry is a kind of Context-Free Grammar.

  • Approved root. No current parent entails this production restriction.

  • Related — context-free grammar, regular grammar, and one-turn pushdown automaton. They provide superclass, subclass, and machine characterization.

Relationships to Other Abstractions

Local relationship map for Linear GrammarParents appear above the current abstraction, mutual partners to the right, and children below. Node labels state whether each abstraction is prime or domain-specific; colors identify relation types.Linear GrammarDOMAINDomain-specific abstraction: Context-Free Grammar — is a kind ofContext-FreeGrammarDOMAIN

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

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

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With

  • Regular grammar. Tell: Uses a consistent one-sided orientation and is less expressive.
  • Context-free grammar. Tell: Allows multiple nonterminals on a production right side.
  • Linear bounded grammar. Tell: A different term associated with context-sensitive computation.
  • Linear syntax. Tell: An informal layout description, not a formal-language class.

References

  • Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/Linear_grammar (revision 1369338604).

The frozen Wikipedia revision is discovery provenance. The retained source set was reviewed for identity, formal or operational relation, and scope. The encyclopedia's structural synthesis is bounded to those claims; a thin authority surface is recorded as a nonblocking source-strengthening repair rather than concealed.