From 6bf4b90c90f15f4ab60833bddf5b5756d1a6b1f6 Mon Sep 17 00:00:00 2001 From: Elizabeth Alexander Hunt Date: Thu, 2 Jul 2026 11:55:17 -0700 Subject: Init --- Homework/cs5300/homework-five/1.excalidraw.png | Bin 0 -> 35547 bytes Homework/cs5300/homework-five/6.excalidraw.png | Bin 0 -> 17224 bytes .../cs5300/homework-five/compilers_assn_5.html | 456 +++++++++++++++++++++ Homework/cs5300/homework-five/compilers_assn_5.org | 157 +++++++ Homework/cs5300/homework-five/compilers_assn_5.pdf | Bin 0 -> 93041 bytes Homework/cs5300/homework-five/compilers_assn_5.tex | 192 +++++++++ Homework/cs5300/homework-five/missfont.log | 22 + 7 files changed, 827 insertions(+) create mode 100644 Homework/cs5300/homework-five/1.excalidraw.png create mode 100644 Homework/cs5300/homework-five/6.excalidraw.png create mode 100644 Homework/cs5300/homework-five/compilers_assn_5.html create mode 100644 Homework/cs5300/homework-five/compilers_assn_5.org create mode 100644 Homework/cs5300/homework-five/compilers_assn_5.pdf create mode 100644 Homework/cs5300/homework-five/compilers_assn_5.tex create mode 100644 Homework/cs5300/homework-five/missfont.log (limited to 'Homework/cs5300/homework-five') diff --git a/Homework/cs5300/homework-five/1.excalidraw.png b/Homework/cs5300/homework-five/1.excalidraw.png new file mode 100644 index 0000000..272aafe Binary files /dev/null and b/Homework/cs5300/homework-five/1.excalidraw.png differ diff --git a/Homework/cs5300/homework-five/6.excalidraw.png b/Homework/cs5300/homework-five/6.excalidraw.png new file mode 100644 index 0000000..1a1caa4 Binary files /dev/null and b/Homework/cs5300/homework-five/6.excalidraw.png differ diff --git a/Homework/cs5300/homework-five/compilers_assn_5.html b/Homework/cs5300/homework-five/compilers_assn_5.html new file mode 100644 index 0000000..6d1a166 --- /dev/null +++ b/Homework/cs5300/homework-five/compilers_assn_5.html @@ -0,0 +1,456 @@ + + + + + + + +Assignment Five + + + + + + + + +
+

Assignment Five

+ +
+

1. 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} + + +
+

1.excalidraw.png +

+
+
+
+ +
+

2. 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} +
+
+ +
+

3. 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} +
+
+ +
+

4. Question Four

+
+\begin{verbatim} +N -> aNbN +N -> bNaN +N -> ε +\end{verbatim} +
+
+ +
+

5. 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} +
+
+ +
+

6. Question Six

+
+

+This one we can actually create from a DFA! +

+ + +
+

6.excalidraw.png +

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

7. Question Seven

+
+

+Consider 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, hen, we can transform S into an equivalent grammar by the following rules for nonterminals or terminals: +

+
+ +
+

7.1. 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} + +

+goes to +

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

7.2. 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} + +

+goes to +

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

7.3. Example(s)

+
+

+For 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 (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} +
+
+
+
+
+

Author: Lizzy Hunt

+

Created: 2023-02-16 Thu 21:18

+

Validate

+
+ + \ No newline at end of file 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} diff --git a/Homework/cs5300/homework-five/compilers_assn_5.pdf b/Homework/cs5300/homework-five/compilers_assn_5.pdf new file mode 100644 index 0000000..399c7ea Binary files /dev/null and b/Homework/cs5300/homework-five/compilers_assn_5.pdf differ 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 diff --git a/Homework/cs5300/homework-five/missfont.log b/Homework/cs5300/homework-five/missfont.log new file mode 100644 index 0000000..669c341 --- /dev/null +++ b/Homework/cs5300/homework-five/missfont.log @@ -0,0 +1,22 @@ +mktextfm Consolas +mktextfm Consolas +mktextfm Consolas +mktextfm Consolas/BI +mktextfm Consolas +mktextfm Consolas/B +mktextfm Consolas +mktextfm Consolas/I +mktextfm Consolas +mktextfm Consolas +mktextfm Consolas +mktextfm Consolas +mktextfm Consolas +mktextfm Consolas +mktextfm Consolas/BI +mktextfm Consolas +mktextfm Consolas/B +mktextfm Consolas +mktextfm Consolas/I +mktextfm Consolas +mktextfm Consolas +mktextfm Consolas -- cgit v1.3