51/110
\begin{frame}{(Strictly) Right Linear Grammars}

\begin{block}{Theorem}
Let $G$ be a right linear grammar $G$.
There exists a \emph{strictly} right linear grammar $H$ such that $L(G) = L(H)$.
\end{block}
\pause

\begin{construction}
Let $G=(V,T,S,P)$ be a right linear grammar.
\pause\smallskip

Assume that we have a production rule $\gamma$ of the form
$\alert{A} ~\alert{\to}~ \alert{u(B)}$
with $A,B \in V$ and $u \in T^*$ with $\alert{|u| > 1}$.
\pause\smallskip

Then \alert{$u = a w$} for some $a \in T$ and $w \in T^+$.
\pause\smallskip

Let \alert{$X$} be a \alert{fresh} variable (that is, $X \not\in (V\cup T)$).
\pause\smallskip

We add $X$ to $V$ and split the rule $\gamma$ into:
\begin{talign}
Then $A \to aX \to aw(B) = u(B)$. It follows $L(G) = L(H)$.
Repeat splitting until $|u| \le 1$ for all rules.