InitHEAD main

author: Elizabeth Alexander Hunt <me@liz.coffee> 2026-07-02 11:55:17 -0700
committer: Elizabeth Alexander Hunt <me@liz.coffee> 2026-07-02 11:55:17 -0700
commit: 6bf4b90c90f15f4ab60833bddf5b5756d1a6b1f6 (patch)
tree: ed97e39ec77c5231ffd2c394493e68d00ddac5a4 /Homework/cs5300/homework-five/compilers_assn_5.html
download: misc-undergrad-6bf4b90c90f15f4ab60833bddf5b5756d1a6b1f6.tar.gz
misc-undergrad-6bf4b90c90f15f4ab60833bddf5b5756d1a6b1f6.zip
1 files changed, 456 insertions, 0 deletions
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 @@
+<?xml version="1.0" encoding="utf-8"?>
+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
+"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
+<html xmlns="http://www.w3.org/1999/xhtml" lang="en" xml:lang="en">
+<head>
+<!-- 2023-02-16 Thu 21:18 -->
+<meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
+<meta name="viewport" content="width=device-width, initial-scale=1" />
+<title>Assignment Five</title>
+<meta name="author" content="Lizzy Hunt" />
+<meta name="generator" content="Org Mode" />
+<style>
+  #content { max-width: 60em; margin: auto; }
+  .title  { text-align: center;
+             margin-bottom: .2em; }
+  .subtitle { text-align: center;
+              font-size: medium;
+              font-weight: bold;
+              margin-top:0; }
+  .todo   { font-family: monospace; color: red; }
+  .done   { font-family: monospace; color: green; }
+  .priority { font-family: monospace; color: orange; }
+  .tag    { background-color: #eee; font-family: monospace;
+            padding: 2px; font-size: 80%; font-weight: normal; }
+  .timestamp { color: #bebebe; }
+  .timestamp-kwd { color: #5f9ea0; }
+  .org-right  { margin-left: auto; margin-right: 0px;  text-align: right; }
+  .org-left   { margin-left: 0px;  margin-right: auto; text-align: left; }
+  .org-center { margin-left: auto; margin-right: auto; text-align: center; }
+  .underline { text-decoration: underline; }
+  #postamble p, #preamble p { font-size: 90%; margin: .2em; }
+  p.verse { margin-left: 3%; }
+  pre {
+    border: 1px solid #e6e6e6;
+    border-radius: 3px;
+    background-color: #f2f2f2;
+    padding: 8pt;
+    font-family: monospace;
+    overflow: auto;
+    margin: 1.2em;
+  }
+  pre.src {
+    position: relative;
+    overflow: auto;
+  }
+  pre.src:before {
+    display: none;
+    position: absolute;
+    top: -8px;
+    right: 12px;
+    padding: 3px;
+    color: #555;
+    background-color: #f2f2f299;
+  }
+  pre.src:hover:before { display: inline; margin-top: 14px;}
+  /* Languages per Org manual */
+  pre.src-asymptote:before { content: 'Asymptote'; }
+  pre.src-awk:before { content: 'Awk'; }
+  pre.src-authinfo::before { content: 'Authinfo'; }
+  pre.src-C:before { content: 'C'; }
+  /* pre.src-C++ doesn't work in CSS */
+  pre.src-clojure:before { content: 'Clojure'; }
+  pre.src-css:before { content: 'CSS'; }
+  pre.src-D:before { content: 'D'; }
+  pre.src-ditaa:before { content: 'ditaa'; }
+  pre.src-dot:before { content: 'Graphviz'; }
+  pre.src-calc:before { content: 'Emacs Calc'; }
+  pre.src-emacs-lisp:before { content: 'Emacs Lisp'; }
+  pre.src-fortran:before { content: 'Fortran'; }
+  pre.src-gnuplot:before { content: 'gnuplot'; }
+  pre.src-haskell:before { content: 'Haskell'; }
+  pre.src-hledger:before { content: 'hledger'; }
+  pre.src-java:before { content: 'Java'; }
+  pre.src-js:before { content: 'Javascript'; }
+  pre.src-latex:before { content: 'LaTeX'; }
+  pre.src-ledger:before { content: 'Ledger'; }
+  pre.src-lisp:before { content: 'Lisp'; }
+  pre.src-lilypond:before { content: 'Lilypond'; }
+  pre.src-lua:before { content: 'Lua'; }
+  pre.src-matlab:before { content: 'MATLAB'; }
+  pre.src-mscgen:before { content: 'Mscgen'; }
+  pre.src-ocaml:before { content: 'Objective Caml'; }
+  pre.src-octave:before { content: 'Octave'; }
+  pre.src-org:before { content: 'Org mode'; }
+  pre.src-oz:before { content: 'OZ'; }
+  pre.src-plantuml:before { content: 'Plantuml'; }
+  pre.src-processing:before { content: 'Processing.js'; }
+  pre.src-python:before { content: 'Python'; }
+  pre.src-R:before { content: 'R'; }
+  pre.src-ruby:before { content: 'Ruby'; }
+  pre.src-sass:before { content: 'Sass'; }
+  pre.src-scheme:before { content: 'Scheme'; }
+  pre.src-screen:before { content: 'Gnu Screen'; }
+  pre.src-sed:before { content: 'Sed'; }
+  pre.src-sh:before { content: 'shell'; }
+  pre.src-sql:before { content: 'SQL'; }
+  pre.src-sqlite:before { content: 'SQLite'; }
+  /* additional languages in org.el's org-babel-load-languages alist */
+  pre.src-forth:before { content: 'Forth'; }
+  pre.src-io:before { content: 'IO'; }
+  pre.src-J:before { content: 'J'; }
+  pre.src-makefile:before { content: 'Makefile'; }
+  pre.src-maxima:before { content: 'Maxima'; }
+  pre.src-perl:before { content: 'Perl'; }
+  pre.src-picolisp:before { content: 'Pico Lisp'; }
+  pre.src-scala:before { content: 'Scala'; }
+  pre.src-shell:before { content: 'Shell Script'; }
+  pre.src-ebnf2ps:before { content: 'ebfn2ps'; }
+  /* additional language identifiers per "defun org-babel-execute"
+       in ob-*.el */
+  pre.src-cpp:before  { content: 'C++'; }
+  pre.src-abc:before  { content: 'ABC'; }
+  pre.src-coq:before  { content: 'Coq'; }
+  pre.src-groovy:before  { content: 'Groovy'; }
+  /* additional language identifiers from org-babel-shell-names in
+     ob-shell.el: ob-shell is the only babel language using a lambda to put
+     the execution function name together. */
+  pre.src-bash:before  { content: 'bash'; }
+  pre.src-csh:before  { content: 'csh'; }
+  pre.src-ash:before  { content: 'ash'; }
+  pre.src-dash:before  { content: 'dash'; }
+  pre.src-ksh:before  { content: 'ksh'; }
+  pre.src-mksh:before  { content: 'mksh'; }
+  pre.src-posh:before  { content: 'posh'; }
+  /* Additional Emacs modes also supported by the LaTeX listings package */
+  pre.src-ada:before { content: 'Ada'; }
+  pre.src-asm:before { content: 'Assembler'; }
+  pre.src-caml:before { content: 'Caml'; }
+  pre.src-delphi:before { content: 'Delphi'; }
+  pre.src-html:before { content: 'HTML'; }
+  pre.src-idl:before { content: 'IDL'; }
+  pre.src-mercury:before { content: 'Mercury'; }
+  pre.src-metapost:before { content: 'MetaPost'; }
+  pre.src-modula-2:before { content: 'Modula-2'; }
+  pre.src-pascal:before { content: 'Pascal'; }
+  pre.src-ps:before { content: 'PostScript'; }
+  pre.src-prolog:before { content: 'Prolog'; }
+  pre.src-simula:before { content: 'Simula'; }
+  pre.src-tcl:before { content: 'tcl'; }
+  pre.src-tex:before { content: 'TeX'; }
+  pre.src-plain-tex:before { content: 'Plain TeX'; }
+  pre.src-verilog:before { content: 'Verilog'; }
+  pre.src-vhdl:before { content: 'VHDL'; }
+  pre.src-xml:before { content: 'XML'; }
+  pre.src-nxml:before { content: 'XML'; }
+  /* add a generic configuration mode; LaTeX export needs an additional
+     (add-to-list 'org-latex-listings-langs '(conf " ")) in .emacs */
+  pre.src-conf:before { content: 'Configuration File'; }
+
+  table { border-collapse:collapse; }
+  caption.t-above { caption-side: top; }
+  caption.t-bottom { caption-side: bottom; }
+  td, th { vertical-align:top;  }
+  th.org-right  { text-align: center;  }
+  th.org-left   { text-align: center;   }
+  th.org-center { text-align: center; }
+  td.org-right  { text-align: right;  }
+  td.org-left   { text-align: left;   }
+  td.org-center { text-align: center; }
+  dt { font-weight: bold; }
+  .footpara { display: inline; }
+  .footdef  { margin-bottom: 1em; }
+  .figure { padding: 1em; }
+  .figure p { text-align: center; }
+  .equation-container {
+    display: table;
+    text-align: center;
+    width: 100%;
+  }
+  .equation {
+    vertical-align: middle;
+  }
+  .equation-label {
+    display: table-cell;
+    text-align: right;
+    vertical-align: middle;
+  }
+  .inlinetask {
+    padding: 10px;
+    border: 2px solid gray;
+    margin: 10px;
+    background: #ffffcc;
+  }
+  #org-div-home-and-up
+   { text-align: right; font-size: 70%; white-space: nowrap; }
+  textarea { overflow-x: auto; }
+  .linenr { font-size: smaller }
+  .code-highlighted { background-color: #ffff00; }
+  .org-info-js_info-navigation { border-style: none; }
+  #org-info-js_console-label
+    { font-size: 10px; font-weight: bold; white-space: nowrap; }
+  .org-info-js_search-highlight
+    { background-color: #ffff00; color: #000000; font-weight: bold; }
+  .org-svg { }
+</style>
+<script>
+  window.MathJax = {
+    tex: {
+      ams: {
+        multlineWidth: '85%'
+      },
+      tags: 'ams',
+      tagSide: 'right',
+      tagIndent: '.8em'
+    },
+    chtml: {
+      scale: 1.0,
+      displayAlign: 'center',
+      displayIndent: '0em'
+    },
+    svg: {
+      scale: 1.0,
+      displayAlign: 'center',
+      displayIndent: '0em'
+    },
+    output: {
+      font: 'mathjax-modern',
+      displayOverflow: 'overflow'
+    }
+  };
+</script>
+
+<script
+  id="MathJax-script"
+  async
+  src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js">
+</script>
+</head>
+<body>
+<div id="content" class="content">
+<h1 class="title">Assignment Five</h1>
+
+<div id="outline-container-orgd749271" class="outline-2">
+<h2 id="orgd749271"><span class="section-number-2">1.</span> Question One</h2>
+<div class="outline-text-2" id="text-1">
+\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}
+
+
+<div id="orgedc3ab8" class="figure">
+<p><img src="./1.excalidraw.png" alt="1.excalidraw.png" />
+</p>
+</div>
+</div>
+</div>
+
+<div id="outline-container-org35f1897" class="outline-2">
+<h2 id="org35f1897"><span class="section-number-2">2.</span> Question Two</h2>
+<div class="outline-text-2" id="text-2">
+\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}
+</div>
+</div>
+
+<div id="outline-container-org2f075dc" class="outline-2">
+<h2 id="org2f075dc"><span class="section-number-2">3.</span> Question Three</h2>
+<div class="outline-text-2" id="text-3">
+\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}
+</div>
+</div>
+
+<div id="outline-container-org733adfa" class="outline-2">
+<h2 id="org733adfa"><span class="section-number-2">4.</span> Question Four</h2>
+<div class="outline-text-2" id="text-4">
+\begin{verbatim}
+N -> aNbN
+N -> bNaN
+N -> ε
+\end{verbatim}
+</div>
+</div>
+
+<div id="outline-container-orgd670219" class="outline-2">
+<h2 id="orgd670219"><span class="section-number-2">5.</span> Question Five</h2>
+<div class="outline-text-2" id="text-5">
+<p>
+\(count(a) \neq count(b) \Rightarrow count(a) > count(b) \vee count(a) < count(b)\)
+</p>
+
+<ul class="org-ul">
+<li>More A's than B's = G</li>
+<li>Less A's than B's = L</li>
+</ul>
+
+\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}
+</div>
+</div>
+
+<div id="outline-container-orgf54c9c6" class="outline-2">
+<h2 id="orgf54c9c6"><span class="section-number-2">6.</span> Question Six</h2>
+<div class="outline-text-2" id="text-6">
+<p>
+This one we can actually create from a DFA!
+</p>
+
+
+<div id="org1a151d7" class="figure">
+<p><img src="./6.excalidraw.png" alt="6.excalidraw.png" />
+</p>
+</div>
+
+\begin{verbatim}
+S -> aN
+N -> aM
+N -> bS
+M -> MM
+M -> a
+\end{verbatim}
+</div>
+</div>
+
+<div id="outline-container-org0ed867b" class="outline-2">
+<h2 id="org0ed867b"><span class="section-number-2">7.</span> Question Seven</h2>
+<div class="outline-text-2" id="text-7">
+<p>
+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:
+</p>
+</div>
+
+<div id="outline-container-orgb149809" class="outline-3">
+<h3 id="orgb149809"><span class="section-number-3">7.1.</span> Kleene Closure</h3>
+<div class="outline-text-3" id="text-7-1">
+<p>
+If we have a match in a production body corresponding to Kleene Closure, then we can transform it into two new productions:
+</p>
+
+\begin{verbatim}
+B*
+\end{verbatim}
+
+<p>
+goes to
+</p>
+
+\begin{verbatim}
+A -> ε
+A -> BA
+\end{verbatim}
+</div>
+</div>
+
+<div id="outline-container-org84f1fcf" class="outline-3">
+<h3 id="org84f1fcf"><span class="section-number-3">7.2.</span> Union</h3>
+<div class="outline-text-3" id="text-7-2">
+<p>
+If we have a match in a production body corresponding to the union operator, then we can rewrite it as two new productions:
+</p>
+
+\begin{verbatim}
+B | C
+\end{verbatim}
+
+<p>
+goes to
+</p>
+
+\begin{verbatim}
+A -> B
+A -> C
+\end{verbatim}
+</div>
+</div>
+
+<div id="outline-container-org1072c90" class="outline-3">
+<h3 id="org1072c90"><span class="section-number-3">7.3.</span> Example(s)</h3>
+<div class="outline-text-3" id="text-7-3">
+<p>
+For example, consider the grammar:
+</p>
+
+\begin{verbatim}
+N -> (A | B)*
+A -> aA
+A -> ε
+B -> bB
+B -> ε
+\end{verbatim}
+
+<p>
+then we can form our first transformation by replacing N (no need to rename since it's already the start symbol):
+</p>
+
+\begin{verbatim}
+N -> ε
+N -> (A | B)N
+A -> aA
+A -> ε
+B -> bB
+B -> ε
+\end{verbatim}
+
+<p>
+which is then further reduced when we transform (A | B)
+</p>
+
+\begin{verbatim}
+N -> ε
+N -> DN
+D -> A
+D -> B
+A -> aA
+A -> ε
+B -> bB
+B -> ε
+\end{verbatim}
+</div>
+</div>
+</div>
+</div>
+<div id="postamble" class="status">
+<p class="author">Author: Lizzy Hunt</p>
+<p class="date">Created: 2023-02-16 Thu 21:18</p>
+<p class="validation"><a href="https://validator.w3.org/check?uri=referer">Validate</a></p>
+</div>
+</body>
+</html>
+\ No newline at end of file
author	Elizabeth Alexander Hunt <me@liz.coffee>	2026-07-02 11:55:17 -0700
committer	Elizabeth Alexander Hunt <me@liz.coffee>	2026-07-02 11:55:17 -0700
commit	6bf4b90c90f15f4ab60833bddf5b5756d1a6b1f6 (patch)
tree	ed97e39ec77c5231ffd2c394493e68d00ddac5a4 /Homework/cs5300/homework-five/compilers_assn_5.html
download	misc-undergrad-6bf4b90c90f15f4ab60833bddf5b5756d1a6b1f6.tar.gz misc-undergrad-6bf4b90c90f15f4ab60833bddf5b5756d1a6b1f6.zip