InitHEADmain

1 files changed, 157 insertions, 0 deletions

diff --git a/Homework/cs5300/homework-five/compilers_assn_5.org b/Homework/cs5300/homework-five/compilers_assn_5.org
new file mode 100644
index 0000000..f89a774
--- /dev/null
+++ b/Homework/cs5300/homework-five/compilers_assn_5.org
@@ -0,0 +1,157 @@
+#+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}