Left Linear Grammar

This is a bit of a detour. Previously, we defined regular grammar as,

$$A \rightarrow aB \\ A \rightarrow a$$

Let's consider another kind of grammar,

$$A \rightarrow Ba \\ A \rightarrow a$$

Because the target has non-terminal on the left side, this grammar is called the left linear grammar. The regular grammar is sometimes called the right linear grammar.

In this section, we need to prove that left linear grammar can yield regular languages.

Proof by automaton

The first proof is done by constructing an FN that tests the language of the left linear grammar. And because FN recognizes regular language, we can prove that left linear grammar generates regular language if there exists such FN.

The construction is done backwards. Let's first define the starting state, $qs$.

For all,

$$A \rightarrow a$$

We create state $A$ if there exists none. Then create an edge from $qs$ to $A$ (please note that this is in a different direction).

Then, for,

$$A \rightarrow Bb$$

We create an edge with label $b$ from $B$ to $A$.

After the construction, we mark $S$ as the accept state.

This automaton will accept the language of the left linear grammar. And because FN yields regular language, the left linear grammar yields regular language.

Why this automaton accepts the language from left linear grammar? For right linear grammar, it is done by derivation- that every transition in the automaton means a derivation. For left linear grammar, it is done by induction.

If,

$$u \Rightarrow v$$

We say,

$$v \Leftarrow u$$

This operation from $v$ to $u$ is called induction.

If a sentence can be inducted to $S$, then it is a sentence in the language.

Let's consider a induction sequence,

$$v_0 \Leftarrow \ldots \Leftarrow v_i \Leftarrow v_{i + 1} \Leftarrow \ldots \Leftarrow v_{n-1} \Leftarrow S$$

For a induction,

$$v_i \Leftarrow v_{i + 1}$$

It can be mapped to the transition,

$$\mathcal{T}(q_i, i@v) = q_{i+1}$$

Because we mapped $S$ into accept state, we can prove that the automaton accepts all sentences generated by the left linear grammar.

Proof by Regularity Preservation under Reverse

Another approach to prove that left linear grammars generate regular languages is by transforming them into right linear grammars through a reversal process. Here's how the construction works:

1. Reverse Productions: For each production in the left linear grammar $G$ , reverse the order of symbols on the right-hand side. Specifically:

   • A production of the form $A \rightarrow B a$ becomes $A \rightarrow a B$ .
   • A production of the form $A \rightarrow a$ remains $A \rightarrow a$ .

2. Construct Right Linear Grammar: The resulting grammar $G'$ from the previous step is a right linear grammar because all productions now conform to the right linear form (non-terminal on the right end, if present).

3. Language Relationship: The language generated by $G'$ , denoted $\mathcal{L}(G')$ , is the reversal of the language generated by $G$ . That is, $\mathcal{L}(G') = \{ w^R \mid w \in \mathcal{L}(G) \}$ .

4. Regularity Preservation: Since $G'$ is a right linear grammar, $\mathcal{L}(G')$ is a regular language. Regular languages are closed under reversal, meaning that if $\mathcal{L}(G')$ is regular, then $\mathcal{L}(G)$ (being the reversal of $\mathcal{L}(G')$ ) is also regular.

To prove that regular languages are closed under reversal, we can use the properties of regular expressions and structural induction. Here's the proof:

1. Regular Languages and Regular Expressions:
   Every regular language $\mathcal{L}$ can be represented by a regular expression $E$ .

2. Reversal of Regular Expressions:
   We define the reversal of a regular expression $E$ , denoted $E^R$ , recursively as follows:

   • Base cases:
     • $\lambda^R = \lambda$ (reversal of the empty string is itself).
     • $a^R = a$ for $a \in \Sigma$ (reversal of a single symbol is itself).
     • $\emptyset^R = \emptyset$ (reversal of the empty language is itself).
   • Inductive cases:
     • Union: $(E + F)^R = E^R + F^R$ .
     • Concatenation: $(EF)^R = F^R E^R$ (reversing the order of concatenation).
     • Kleene star: $(E^*)^R = (E^R)^*$ .

3. Reversal Preserves Regularity:
   By structural induction on $E$ :

   • Base cases: $\lambda$ , $a$ , and $\emptyset$ are regular expressions, and their reversals are trivially regular.
   • Union: If $E$ and $F$ are regular, then $E^R + F^R$ is regular (union of regular languages is regular).
   • Concatenation: If $E$ and $F$ are regular, then $F^R E^R$ is regular (concatenation of regular languages is regular).
   • Kleene star: If $E$ is regular, then $(E^R)^*$ is regular (Kleene star of a regular language is regular).

4. Conclusion:
   The reversal of a regular expression $E^R$ is also a regular expression. Therefore, the language $\mathcal{L}^R = \{ w^R \mid w \in \mathcal{L} \}$ is regular.
   Hence, regular languages are closed under reversal.

In all, we can prove that left linear grammar is equivalent to right linear grammar, thus generates regular language.