#+TITLE: Assignment Three
#+AUTHOR: Lizzy Hunt
#+STARTUP: entitiespretty fold inlineimages
#+LATEX_HEADER: \notindent \notga \usepackage{ dsfont } \usepackage{amsmath} \usepackage[a4paper,margin=1in,landscape]{geometry}
#+LATEX: \setlength\parindent{0pt}
#+OPTIONS: toc:nil

* Question One
** a
#+attr_latex: :width 250px
[[./1a.excalidraw.png]]
** b
#+attr_latex: :width 250px
[[./1b.excalidraw.png]]
** c
#+attr_latex: :width 250px
[[./1c.excalidraw.png]]
** d
#+attr_latex: :width 250px
[[./1d.excalidraw.png]]
** e
#+attr_latex: :width 250px
[[./1e.excalidraw.png]]
** f
#+attr_latex: :width 200px
[[./1f.excalidraw.png]]

* Question Two
| State | a      | b   | e      |
|     0 | \phi      | \phi   | {1, 3} |
|     1 | {2, 4} | {4} | \phi      |
|     2 | {2}    | \phi   | \phi      |
|     3 | \phi      | {4} | \phi      |
|     4 | \phi      | {4} | \phi      |

* Question Three
| State | a | b |
|     0 | 1 | 0 |
|     1 | 1 | 2 |
|     2 | 1 | 3 |
|     3 | 1 | 0 |

* Question Four
** a
#+attr_latex: :width 350px
[[./4a.excalidraw.png]]
** b
| DFA State | NFA States               | a             | b                             | c                             |
| d_0        | {s_0, s_1, s_2, s_5, s_9}     | {s_3, s_6} (d_1) | s_e                            | s_e                            |
| d_1        | {s_3, s_6}                 | s_e            | {s_4, s_8, s_9, s_1, s_2, s_5} (d_2) | {s_7, s_8, s_9, s_1, s_2, s_5} (d_3) |
| d_2        | {s_4, s_8, s_9, s_1, s_2, s_5} | {s_3, s_6} (d_1) | s_e                            | s_e                            |
| d_3        | {s_7, s_8, s_9, s_1, s_2, s_5} | {s_3, s_6} (d_1) | s_e                            | s_e                            |

#+attr_latex: :width 200px
[[./4b.excalidraw.png]]
** c
| partition            | a                           | b                        | c                        |
| {d_1}, {d_0, d_2, d_3}   | {d_0, d_2, d_3} \Rightarrow {d_1, d_0, d_0} | {d_0, d_2, d_3} \Rightarrow {-, -, -} | {d_0, d_2, d_3} \Rightarrow {-, -, -} |
| {d_1}, {d_0}, {d_2, d_3} | {d_2, d_3} \Rightarrow {d_0, d_0}         | {d_2, d_3} \Rightarrow {-, -}        | {d_2, d_3} \Rightarrow {-, -}        |

#+attr_latex: :width 200px
[[./4c.excalidraw.png]]

* Question Five
** regex 1
*** NFA
#+attr_latex: :width 350px
[[./51a.excalidraw.png]]

*** DFA
| DFA State | NFA States               | 1                             | 0                             |
| d_0        | {s_0, s_1, s_2, s_4, s_7}     | {s_1, s_2, s_3, s_4, s_6, s_7} (d_1) | {s_1, s_2, s_4, s_5, s_6, s_7} (d_2) |
| d_1        | {s_1, s_2, s_3, s_4, s_6, s_7} | d_1                            | d_2                            |
| d_2        | {s_1, s_2, s_4, s_5, s_6, s_7} | d_1                            | d_2                            |

#+attr_latex: :width 200px
[[./51b.excalidraw.png]]

*** Minimization
| partition    |                           1 |                           0 |
| {d_0, d_1, d_2} | {d_0, d_1, d_2} \Rightarrow {d_1, d_1, d_1} | {d_0, d_1, d_2} \Rightarrow {d_2, d_2, d_2} |

#+attr_latex: :width 75px
[[./51c.excalidraw.png]]

** regex 2
*** NFA
#+attr_latex: :width 350px
[[./52a.excalidraw.png]]
*** DFA
| DFA State | NFA States                                  | 1                                                | 0                                           |
| d_0        | {s_0, s_1, s_2, s_3, s_5, s_11, s_6, s_12 }         | {s_1, s_2, s_3, s_5, s_6, s_7, s_8, s_10, s_11, s_12} (d_1) | {s_1, s_2, s_3, s_4, s_5, s_11, s_6, s_12} (d_2)     |
| d_1        | {s_1, s_2, s_3, s_5, s_6, s_7, s_8, s_10, s_11, s_12} | d_1                                               | {s_1, s_2, s_3, s_4, s_5, s_9, s_11, s_6, s_12} (d_3) |
| d_2        | {s_1, s_2, s_3, s_4, s_5, s_11, s_6}               | d_1                                               | d_2                                          |
| d_3        | {s_1, s_2, s_3, s_4, s_5, s_9, s_11, s_6, s_12}      | d_1                                               | d_2                                          |

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

*** Minimization
| partition        |                                   1 |                                   0 |
| {d_0, d_1, d_2, d_3} | {d_0, d_1, d_2, d_3} \Rightarrow {d_1, d_1, d_1, d_1} | {d_0, d_1, d_2, d_3} \Rightarrow {d_2, d_3, d_2, d_2} |

#+attr_latex: :width 100px
[[./52c.excalidraw.png]]

* Question Six
** a
*** DFA
#+attr_latex: :width 350px
[[./6a.excalidraw.png]]

*** catMap
#+BEGIN_SRC json
{
  '-': 'sign',
  '+': 'sign',
  [0-9]: 'digit',
  'e': 'scntfc'
}
#+END_SRC

*** transMap
#+BEGIN_SRC json
{
  's0': {
    'sign': 's1',
    'digit': 's2',
  },
  's1': {
    'digit': 's2',
  },
  's2': {
    'digit': 's2',
    'scntfc': 's3',
  },
  's3': {
    'sign': 's4',
    'digit': 's5',
  },
  's4': {
    'digit': 's6',
  },
  's5': {
    'digit': 's6',
  },
  's6': {
    'digit': 's6',
  },
}
#+END_SRC

*** tokenTypes
#+BEGIN_SRC json
{
  's2': 'integer',
  's6': 'integer,
}
#+END_SRC
** b
*** DFA
#+attr_latex: :width 200px
[[./6b.excalidraw.png]]

*** catMap
#+BEGIN_SRC json
{
  [a-zA-Z]: 'letter',
  '_': 'letter',
  [0-9]: 'digit',
}
#+END_SRC

*** transMap
#+BEGIN_SRC json
{
  's1': {
    'letter': 's2'
  },
  's2': {
    'letter': 's2',
    'digit': 's2',
  },
}
#+END_SRC

** c
*** DFA
#+attr_latex: :width 400px
[[./6c.excalidraw.png]]

*** catMap
#+BEGIN_SRC json
{
  [^(\n)*/]: 'nonc',
  '\n': 'newline',
  'eof': 'eof',
  '/': 'slash',
  '*': 'star'
}
#+END_SRC
*** transMap
#+BEGIN_SRC json
{
  's0': {
    'slash': 's1',
  },
  's1': {
    'slash': 's2',
    'star': 's4',
  },
  's2': {
    'nonc': 's2',
    'newline': 's3',
    'eof': 's3'
  },
  's4': {
    'nonc': 's4',
    'star': 's5',
  },
  's5': {
    'nonc': 's4',
    'newline': 's4',
    'slash': 's6'
  }
}
#+END_SRC

*** tokenType
#+BEGIN_SRC json
{
  's3': 'singleLineComment',
  's6': 'multiLineComment',
}
#+END_SRC