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

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 \rightarrow \alpha$,
• the string $\alpha$ contains terminals and at most one nonterminal symbol (e.g., patterns like $A \rightarrow uBv$ or $A \rightarrow w$ where $u,v,w$ are strings of terminals, and $B$ is a nonterminal).

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

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

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