1 files changed, 192 insertions, 0 deletions
diff --git a/Homework/cs5300/homework-five/compilers_assn_5.tex b/Homework/cs5300/homework-five/compilers_assn_5.tex
new file mode 100644
index 0000000..160bb9a
--- /dev/null
+++ b/Homework/cs5300/homework-five/compilers_assn_5.tex
@@ -0,0 +1,192 @@
+% 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}
+\ No newline at end of file