Variable-based grammar

A variable-based grammar has disjoint finite terminal and variable alphabets $\Sigma ,V$, a start variable $S\in V$, and productions $\alpha \to \beta$ in which $\alpha ,\beta \in (\Sigma \cup V{)}^{\ast }$ and $\alpha$ contains at least one variable.

A nonterminal is unreachable when no word derivable from the start symbol contains it. Productions whose left sides are unreachable do not affect the generated language.

A nonterminal is nonproductive when no word derived from it consists entirely of terminal symbols. Every derivation containing such a symbol therefore fails to produce a word in the generated language.

A right-linear regular grammar has productions of the forms $A\to wB$ and $A\to w$, where $A,B$ are variables and $w$ is a terminal word.

Every sentential form reachable from the start variable of a right-linear grammar is either a terminal word $w$ or $wA$, where $A$ is the unique variable and occurs at the right end.

A variable $A$ is accessible when $S{\Rightarrow }^{\ast }wA$ for some terminal word $w$.

A variable $A$ is looping when $A{\Rightarrow }^{\ast }wA$ for some terminal word $w$ through a nonempty derivation.

A variable $A$ is terminable when $A{\Rightarrow }^{\ast }w$ for some terminal word $w$.

If a finite right-linear grammar generates an infinite language, some variable is accessible, looping, and terminable. It is the repeated variable on a sufficiently long accepting derivation.

For grammars $G=(\Sigma ,V,P,S)$ and $G^{\prime }=(\Sigma ,V^{\prime },P^{\prime },S^{\prime })$ with disjoint variable sets, introduce a new variable $S_0$ and setIf both input grammars are variable based, then $L(H)=L(G)L(G^{\prime })$.

Retain every production $\alpha \to \beta$ of $P$ whose right-hand side contains a variable, replace every production $\alpha \to w$ with $w\in {\Sigma }^{\ast }$ by $\alpha \to w{S}^{\prime }$, include $P^{\prime }$, and use $S$ as start variable. If $G$ and $G^{\prime }$ are right-linear, the resulting grammar is right-linear and generates $L(G)L(G^{\prime })$.

The regular construction relies on a regular derivation having exactly one terminal rule, at its end. In a general variable-based grammar several variables may each use terminal productions, so replacing every such production can introduce several copies of the second start variable.

Even if both input grammars are regular, the added production $S_0\to S{S}^{\prime }$ has two variables on its right-hand side and therefore need not be a regular production.