#+TITLE: Assignment Five
#+AUTHOR: Lizzy Hunt
#+STARTUP: entitiespretty fold inlineimages
#+LATEX_HEADER: \notindent \notga \usepackage{ dsfont } \usepackage[utf8]{inputenc}  \usepackage{amsmath} \usepackage{fontspec} \usepackage[a4paper,margin=1in,portrait]{geometry} \usepackage{fontspec} \setmonofont{DejaVu Sans Mono}
#+LATEX:  \setlength\parindent{0pt}
#+LATEX_COMPILER: lualatex
#+OPTIONS: toc:nil

* Question One
\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}
  

#+attr_latex: :width 225px
[[./1.excalidraw.png]]

* Question Two
\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}

* Question Three
\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}

* Question Four
\begin{verbatim}
N -> aNbN
N -> bNaN
N -> ε
\end{verbatim}

* Question Five
$count(a) \neq count(b) \Rightarrow count(a) > count(b) \vee count(a) < count(b)$

+ More A's than B's = G
+ Less A's than B's = L

\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}

* Question Six
This one we can actually create from a DFA!

#+attr_latex: :width 150px
[[./6.excalidraw.png]]

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

* Question Seven
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:

** Kleene Closure
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}

** Union
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}

** Example
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}