#import "@preview/finite:0.5.1": automaton
#show link: it => underline(it)
#show link: set text(fill: blue)
#show heading: set text(font: "Noto Sans")
#show raw: set text(font: "JetBrains Mono", ligatures: true)

// helper function, full width sepearator with two newlines
#let separator() = [
  \
  #line(stroke: 0.5pt + black, length: 100%)
  \
]

#let framed(body) = box(stroke: 1pt, inset: 6pt, body)

= Computer Engineering - Sheet 04
\
#underline("Group Members:") \
Jan Meyer: `664237` \
Luke Ethe: `665250` \
\
#underline("Information about this document:") \
This document was created using #link("https://typst.app", "typst").
The original typst file can be found
#link("https://gist.jnmr.dev/jan/CompEngSheet04", "here") \;
a copy of the documents source code has been appended to the end of the PDF.\
No AI / LLM was used for the content of the answers.

#separator()

== Exercise 4-1: Types of Automata
=== _a)_
_Moore-Automata:_ Automata the output of which depends only on
its current state. The outputs are placed inside the state.
The Moore automata is also slower, as it reacts to inputs once clock cycle later
and it's state and output are generated synchronously.

_Mealy-Automata:_ Automata the output of which depends on both its state and
present input. The outputs are placed on transitions, rather than inside the
state - we get something like "$1 slash 0$" (if input $1$, output $0$ and
transition). \
Mealy automata react faster to inputs and generates its output asynchronously.

$arrow.double$ While Moore automata are easier to build, Mealy automata tend to
be faster and more efficient. A Moore automata is easier to design while a mealy
automata trades of that simplicity for a faster output and fewer necessary states.

*Examples:*
Here we have an example on how to build a "Rising Edge Detector" (RED) as a
Mealy-automaton or as a Moore-automaton. \
The RED detects when an input shifts from zero to one and outputs $bold(1)$ only when
that change actually occurs, otherwise $bold(0)$.

#grid(
  columns: (1fr, auto, 2fr, auto, 1fr),
  align: bottom,
  column-gutter: 1.5em,
  [],
  figure(
    automaton(
      (
        s0: (s0: [$0 slash 0$], s1: [$1 slash 1$]),
        s1: (s0: [$0 slash 0$], s1: [$1 slash 0$]),
      ),
      initial: "s0",
      final: (),
    ),
    caption: [Mealy-automaton],
    numbering: none,
  ),
  [],
  figure(
    automaton(
      (
        A: (A: $0$, B: $1$),
        B: (A: $0$, C: $1$),
        C: (A: $0$, C: $1$),
      ),
      initial: "A",
      labels: (A: "A/0", B: "B/1", C: "C/0"),
      final: (),
    ),
    caption: [Moore-automaton],
    numbering: none,
  ),
  [],
)

#pagebreak()
=== _b)_
To convert a Moore-automaton to a Mealy automaton you first copy all the states
and transitions. Then look at each transition and look at the target states
output and write the transition in the form of "Input / Output" and remove the
output from the target state. Finally you minimize as often there are duplicate
states that can be merged.

#figure(
  automaton(
    (
      Q0: (Q0: 1, Q1: 0),
      Q1: (Q0: 0, Q2: 1),
      Q2: (Q1: 1, Q2: 0),
    ),
    initial: (),
    final: (),
    labels: (
      Q0: $Q_0 slash a$,
      Q1: $Q_1 slash b$,
      Q2: $Q_2 slash b$,
    ),
  ),
  supplement: "Step",
  caption: [Copy all the states and transitions],
)

#figure(
  automaton(
    (
      Q0: (Q0: $1 slash a$, Q1: $0 slash b$),
      Q1: (Q0: $0 slash a$, Q2: $1 slash b$),
      Q2: (Q1: $1 slash b$, Q2: $0 slash b$),
    ),
    initial: (),
    final: (),
  ),
  supplement: "Step",
  caption: [Move the output from states to transitions],
)

Here we are already done because we cannot minify as all the states are
distinguishable.


#pagebreak()
== Exercise 4-2: Sequence Detection

#pagebreak()
= Document source code:
#separator()
#raw(read("sheet04_665250_664237.typ"), block: true, lang: "typ")