\begin{frame}{From Right Linear Grammars to NFAs} \begin{goal}{} For every right linear grammar $G$ there exists an NFA $M$ with \begin{talign} L(M) = L(G) \end{talign} \end{goal} \pause \begin{construction}[$\Leftarrow$] Let $G=(V,T,S,P)$ be a right linear grammar. \pause\medskip Make $G$ to \alert{strictly} right linear. Then all rules are of the form \begin{talign} \alert{A \to u} \quad\text{or}\quad \alert{A \to uB} \end{talign} for $A,B \in V$, $u \in (T\cup \{\lambda\})$. \pause Let NFA $M=(Q,\Sigma,\delta,\alert{\{\,S\,\}},F)$ with \begin{talign} \alert{\Sigma = T} && \alert{Q = V \cup \{\,\Omega\,\}} && \alert{F = \{\,\Omega\,\}} \end{talign} where $\Omega \not\in V$. \pause The transitions $\alert{\delta}$ are given by \begin{talign} A &\stackrel{u}{\to} B &&\text{for every $A \to uB$ in $G$}\\[-1mm] A &\stackrel{u}{\to} \Omega &&\text{for every $A \to u$ in $G$} \end{talign} \pause Then $S \Rightarrow^*w \in T^*$ $\iff$ $M$ accepts $w$. \pause Hence $L(G) = L(M)$. \end{construction} \end{frame}