Coursify

Linear Grammar in the Chomsky Hierarchy (CF Grammar with ≤ 1 Nonterminal on RHS)

Linear Grammar in the Chomsky Hierarchy (CF Grammar with ≤ 1 Nonterminal on RHS)

Verified Sources
Sep 12, 2026

A context-free grammar in which each production’s right-hand side contains at most one non-terminal is called a Linear Grammar. This is the defining property that matches the statement in the question: “atmost one non-terminal in the right handside of the production.”

In the Chomsky hierarchy, linear grammars sit strictly between regular grammars and context-free grammars (more permissive than regular, but more restrictive than general CFGs). The key structural restriction is about how many nonterminals can appear on the RHS of any production.

A common way to express the linear grammar constraint:

  • For productions of the form A→αA \rightarrow \alpha,
  • the string α\alpha contains terminals and at most one nonterminal symbol (e.g., patterns like A→uBvA \rightarrow uBv or A→wA \rightarrow w where u,v,wu,v,w are strings of terminals, and BB is a nonterminal).

Mermaid view of “allowed” versus “forbidden” shapes:

Therefore, among the options, the correct answer is (i) linear grammar.

Linear grammars vs regular grammars (intro)

Answer to the MCQ

The blank is “linear grammar”.

  • (i) linear grammar ✅
  • (ii) linear bounded grammar ❌ (that term is typically associated with linearly bounded automata/languages; not the standard grammar restriction in the question)
  • (iii) regular grammar ❌ (regular grammars are more restrictive: they effectively allow nonterminals in a much more limited positional form; they are a subset of linear grammars)
  • (iv) None of the above ❌

Why (i) matches the definition

A linear grammar is defined by the “at most one nonterminal on the RHS” rule, which is exactly what the question states.

Key terms:

  • Linear Grammar
  • Context-Free Grammar (CFG)
  • Regular Grammar

Quick identification procedure for the blank

  1. 1
    Step 1

    Check whether every production’s RHS contains “at most one non-terminal.”

  2. 2
    Step 2

    If the RHS has ≤ 1 nonterminal for all productions, classify it as a Linear Grammar.

  3. 3
    Step 3

    If it were regular, the structure would have stronger positional constraints; but the question only specifies the “≤ 1 nonterminal” constraint.

Placement in the Chomsky hierarchy

Most restrictive (among the listed)

Regular

Productions are left-linear or right-linear; nonterminals appear in limited positions."

Between regular and full CFG

Linear

Each production has at most one nonterminal on the RHS."

General CFG

Context-Free

RHS may contain multiple nonterminals (no “≤ 1” restriction)."

Pro Tip

When a question states a grammar restriction like “at most one nonterminal in RHS,” think first of linear grammars—it’s a standard characterization used in automata/Chomsky hierarchy questions.

Common pitfall

“Linear bounded grammar” is not the usual name for the “≤ 1 nonterminal on RHS” grammar class. Don’t confuse this with “linear” used in other contexts (e.g., boundedness constraints) or with regularity.

Concept check (FAQs)

Knowledge Check

Question 1 of 3
Q1Single choice

A CFG in which every production has at most one non-terminal on its RHS is called:

Explore Related Topics

1

Understanding the MCQ: Compiler, Interpreter, Loader/Linker, or None?

The MCQ conflates formal‑machine concepts (a Turing‑like Machine MM with an unbounded tape) with programming‑language tools, making “None of the mentioned” the only academically correct choice.

  • An infinite tape is a modeling assumption; any actual computation uses only a finite portion.
  • Compilers translate whole programs, interpreters execute statements incrementally, and loaders/linkers build/run executables—they do not bound the tape.
  • An “infinite language” is a set of strings, not a single infinite input to MM.
  • The correct answer is  (iv) None of the mentioned .\,\boxed{\text{(iv) None of the mentioned}}\,.
  • In exams, identify domain mismatches and choose the option that rejects the inconsistency.
2

Which Grammar Type Is the Most Powerful? Understanding Type-0, Type-1, Type-2, and Type-3 Grammars

The most expressive grammar in the Chomsky hierarchy is the unrestricted Type‑0 grammar, which generates all recursively enumerable languages and matches the power of a Turing machine.

  • The hierarchy is strict: L3⊂L2⊂L1⊂L0L_3 \subset L_2 \subset L_1 \subset L_0, so each higher type can generate everything the lower types can, plus more.
  • Type‑3 (regular) → finite automaton; Type‑2 (context‑free) → pushdown automaton; Type‑1 (context‑sensitive) → linear‑bounded automaton; Type‑0 (unrestricted) → Turing machine.
  • Example languages: {anbn∣n≥0}\{a^n b^n \mid n \ge 0\} is context‑free but not regular; {anbncn∣n≥1}\{a^n b^n c^n \mid n \ge 1\} is context‑sensitive but not context‑free.
  • “More powerful” refers to expressive capacity (ability to generate a larger class of languages), not ease of parsing or practical use.
3

Proving That a Grammar Is LL(1) but Not SLR(1)

Browse all research articles