\begin{frame}{(Strictly) Right Linear Grammars}
    Let $G$ be a right linear grammar $G$.
    There exists a \emph{strictly} right linear grammar $H$ such that $L(G) = L(H)$.
    Let $G=(V,T,S,P)$ be a right linear grammar.
    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}$.

    Then \alert{$u = a w$} for some $a \in T$ and $w \in T^+$.
    Let \alert{$X$} be a \alert{fresh} variable (that is, $X \not\in (V\cup T)$).

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