% Created 2023-02-16 Thu 21:32
% Intended LaTeX compiler: lualatex
\documentclass[11pt]{article}
\usepackage{graphicx}
\usepackage{longtable}
\usepackage{wrapfig}
\usepackage{rotating}
\usepackage[normalem]{ulem}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{capt-of}
\usepackage{hyperref}
\notindent \notga \usepackage{ dsfont } \usepackage[utf8]{inputenc}  \usepackage{amsmath} \usepackage{fontspec} \usepackage[a4paper,margin=1in,portrait]{geometry} \usepackage{fontspec} \setmonofont{DejaVu Sans Mono}
\author{Lizzy Hunt}
\date{\today}
\title{Assignment Five}
\hypersetup{
 pdfauthor={Lizzy Hunt},
 pdftitle={Assignment Five},
 pdfkeywords={},
 pdfsubject={},
 pdfcreator={Emacs 28.2 (Org mode 9.6.1)}, 
 pdflang={English}}
\begin{document}

\maketitle
\setlength\parindent{0pt}

\section{Question One}
\label{sec:org921f457}
\begin{verbatim}
N -> N a N b N
  -> ε a N b N (using N -> ε)
  -> ε a N a N b N b N (using N -> N a N b N)
  -> ε a N a N b N a N b N b N (using N -> N a N b N)
  -> ε a ε a N b N a N b N b N (using N -> ε)
  -> ε a ε a ε b N a N b N b N (using N -> ε)
  -> ε a ε a ε b ε a N b N b N (using N -> ε)
  -> ε a ε a ε b ε a ε b N b N (using N -> ε)
  -> ε a ε a ε b ε a ε b ε b N (using N -> ε)
  -> ε a ε a ε b ε a ε b ε b ε (using N -> ε)
  -> aababb (remove epsilons for clarity)
\end{verbatim}


\begin{center}
\includegraphics[width=225px]{./1.excalidraw.png}
\end{center}

\section{Question Two}
\label{sec:org8175f4b}
\begin{verbatim}
N -> N N
  -> N * N (using N -> N *)
  -> (N) * N (using N -> (N))
  -> (N + N) * N (using N -> N + N)
  -> (a + N) * N (using N -> a)
  -> (a + a) * N (using N -> a)
  -> (a + a) * a (using N -> a)
\end{verbatim}

\section{Question Three}
\label{sec:org30f8f3d}
\begin{verbatim}
N -> b N a N
  -> b ε a N (using N -> ε)
  -> b ε a a N b N (using N -> a N b N)
  -> b ε a a a N b N b N (using N -> a N b N)
  -> b ε a a a ε b N b N (using N -> ε)
  -> b ε a a a ε b ε b N (using N -> ε)
  -> b ε a a a ε b ε b ε (using N -> ε)
\end{verbatim}

\section{Question Four}
\label{sec:orgc6e6679}
\begin{verbatim}
N -> aNbN
N -> bNaN
N -> ε
\end{verbatim}

\section{Question Five}
\label{sec:orgef2e893}
\(count(a) \neq count(b) \Rightarrow count(a) > count(b) \vee count(a) < count(b)\)

\begin{itemize}
\item More A's than B's = G
\item Less A's than B's = L
\end{itemize}

\begin{verbatim}
S -> G 
S -> L
G -> GG
G -> EAE
L -> LL
L -> EBE
E -> aEaE
E -> bEaE
E -> ε
A -> aA
A -> a
B -> bB
B -> b
\end{verbatim}

\section{Question Six}
\label{sec:orgfe19196}
This one we can actually create from a DFA!

\begin{center}
\includegraphics[width=150px]{./6.excalidraw.png}
\end{center}

\begin{verbatim}
S -> aN
N -> aM
N -> bS
M -> MM
M -> a
\end{verbatim}

\section{Question Seven}
\label{sec:org2dfc6f9}
A grammar, S, with regular expressions in its production's bodies, after replacing any extensions on regular expressions with their corresponding algebraic equivalents as given in 3.3.5, then, we can transform S into an equivalent grammar by the following rules for nonterminals or terminals:

\subsection{Kleene Closure}
\label{sec:orgdac51cc}
If we have a match in a production body corresponding to Kleene Closure, then we can transform it into two new productions:

\begin{verbatim}
B*
\end{verbatim}

is mapped to

\begin{verbatim}
A -> ε
A -> BA
\end{verbatim}

\subsection{Union}
\label{sec:org1941049}
If we have a match in a production body corresponding to the union operator, then we can rewrite it as two new productions:

\begin{verbatim}
B | C
\end{verbatim}

is mapped to

\begin{verbatim}
A -> B
A -> C
\end{verbatim}

\subsection{Example}
\label{sec:org0ac391e}
Consider the grammar:

\begin{verbatim}
N -> (A | B)*
A -> aA
A -> ε
B -> bB
B -> ε
\end{verbatim}

then we can form our first transformation by replacing N (with no need to rename since it's already the start symbol):

\begin{verbatim}
N -> ε
N -> (A | B)N
A -> aA
A -> ε
B -> bB
B -> ε
\end{verbatim}

which is then further reduced when we transform (A | B)

\begin{verbatim}
N -> ε
N -> DN
D -> A
D -> B
A -> aA
A -> ε
B -> bB
B -> ε
\end{verbatim}
\end{document}