Regular Grammars

We know that formal languages generate strings in a language. Grammars that generate regular languages have a special form, which naturally corresponds to a finite automaton.

To illustrate, the NFA given above, which accepts strings of ones and zeros with a one in the third-to-last place (assuming $\Sigma = \{0,1\}$), appears below with the states renamed for convenience.

The state names serve as variable names in the grammar. From state $S$ we can loop on $S$ with either character, or we can move to state $X$ with a $1$. The following rewrite rule expresses this in formal grammar terms:

$S \rightarrow 0S \;|\; 1S \;|\; X$

We can similarly express the transitions from $X$ and $Y$. Since $Z$ is a final state, we allow it to be replaced by the empty string, meaning that the generation of symbols may terminate. The complete grammar appears below:

$$\begin{align*} S & \to 0S \;|\; 1S \; | \; 1X \\ X & \rightarrow 0Y \; | \; 1Y \\ Y & \rightarrow 0Z \; | \; 1Z \\ Z & \rightarrow \lambda \end{align*}$$

Observe the clear correspondence to the NFA. The from-state appears alone on the left, and the to-states appear on the right, preceded by the symbol from the appropriate edge. This is an example of a right-linear grammar. It is “linear” because only one variable appears on each right-hand side. It is “right-linear” because the variable appears last (i.e., on the right end) of each replacement rule. We can derive a sample string as follows:

$$S \Rightarrow 0S \Rightarrow 01X \Rightarrow 010Y \Rightarrow 0100Z \Rightarrow 0100$$

Right linear grammar: Formal definition

A right-linear grammar is a formal grammar where there is at most one variable on the right-hand side of any rule, and if present, it is the rightmost symbol of the rule.

More formally, rules in a right-linear grammar are of form $V \to sX$ or $V \to s$, where $V$ and $X$ are variables and $s$ is any string in $\Sigma^*$ (i.e., $s$ contains no variables).

Examples of right-linear grammars

Suppose that we want to generate strings of ones and zeros representing binary numbers congruent to $1 \bmod 3$. We start with the automata shown in the following figure.

We begin by renaming the states and making the state where the remainder module $3$ is $1$ the accepting state ($Z$ for $0$ ...