TUHH - Computer Engineering - Sheet 04

sheet04_665250_664237.typ · 3.8 KiB · Typst Raw

#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")

1	#import "@preview/finite:0.5.1": automaton
2	#show link: it => underline(it)
3	#show link: set text(fill: blue)
4	#show heading: set text(font: "Noto Sans")
5	#show raw: set text(font: "JetBrains Mono", ligatures: true)
6
7	// helper function, full width sepearator with two newlines
8	#let separator() = [
9	\
10	#line(stroke: 0.5pt + black, length: 100%)
11	\
12	]
13
14	#let framed(body) = box(stroke: 1pt, inset: 6pt, body)
15
16	= Computer Engineering - Sheet 04
17	\
18	#underline("Group Members:") \
19	Jan Meyer: `664237` \
20	Luke Ethe: `665250` \
21	\
22	#underline("Information about this document:") \
23	This document was created using #link("https://typst.app", "typst").
24	The original typst file can be found
25	#link("https://gist.jnmr.dev/jan/CompEngSheet04", "here") \;
26	a copy of the documents source code has been appended to the end of the PDF.\
27	No AI / LLM was used for the content of the answers.
28
29	#separator()
30
31	== Exercise 4-1: Types of Automata
32	=== _a)_
33	_Moore-Automata:_ Automata the output of which depends only on
34	its current state. The outputs are placed inside the state.
35	The Moore automata is also slower, as it reacts to inputs once clock cycle later
36	and it's state and output are generated synchronously.
37
38	_Mealy-Automata:_ Automata the output of which depends on both its state and
39	present input. The outputs are placed on transitions, rather than inside the
40	state - we get something like "$1 slash 0$" (if input $1$, output $0$ and
41	transition). \
42	Mealy automata react faster to inputs and generates its output asynchronously.
43
44	$arrow.double$ While Moore automata are easier to build, Mealy automata tend to
45	be faster and more efficient. A Moore automata is easier to design while a mealy
46	automata trades of that simplicity for a faster output and fewer necessary states.
47
48	Examples:
49	Here we have an example on how to build a "Rising Edge Detector" (RED) as a
50	Mealy-automaton or as a Moore-automaton. \
51	The RED detects when an input shifts from zero to one and outputs $bold(1)$ only when
52	that change actually occurs, otherwise $bold(0)$.
53
54	#grid(
55	columns: (1fr, auto, 2fr, auto, 1fr),
56	align: bottom,
57	column-gutter: 1.5em,
58	[],
59	figure(
60	automaton(
61	(
62	s0: (s0: [$0 slash 0$], s1: [$1 slash 1$]),
63	s1: (s0: [$0 slash 0$], s1: [$1 slash 0$]),
64	),
65	initial: "s0",
66	final: (),
67	),
68	caption: [Mealy-automaton],
69	numbering: none,
70	),
71	[],
72	figure(
73	automaton(
74	(
75	A: (A: $0$, B: $1$),
76	B: (A: $0$, C: $1$),
77	C: (A: $0$, C: $1$),
78	),
79	initial: "A",
80	labels: (A: "A/0", B: "B/1", C: "C/0"),
81	final: (),
82	),
83	caption: [Moore-automaton],
84	numbering: none,
85	),
86	[],
87	)
88
89	#pagebreak()
90	=== _b)_
91	To convert a Moore-automaton to a Mealy automaton you first copy all the states
92	and transitions. Then look at each transition and look at the target states
93	output and write the transition in the form of "Input / Output" and remove the
94	output from the target state. Finally you minimize as often there are duplicate
95	states that can be merged.
96
97	#figure(
98	automaton(
99	(
100	Q0: (Q0: 1, Q1: 0),
101	Q1: (Q0: 0, Q2: 1),
102	Q2: (Q1: 1, Q2: 0),
103	),
104	initial: (),
105	final: (),
106	labels: (
107	Q0: $Q_0 slash a$,
108	Q1: $Q_1 slash b$,
109	Q2: $Q_2 slash b$,
110	),
111	),
112	supplement: "Step",
113	caption: [Copy all the states and transitions],
114	)
115
116	#figure(
117	automaton(
118	(
119	Q0: (Q0: $1 slash a$, Q1: $0 slash b$),
120	Q1: (Q0: $0 slash a$, Q2: $1 slash b$),
121	Q2: (Q1: $1 slash b$, Q2: $0 slash b$),
122	),
123	initial: (),
124	final: (),
125	),
126	supplement: "Step",
127	caption: [Move the output from states to transitions],
128	)
129
130	Here we are already done because we cannot minify as all the states are
131	distinguishable.
132
133
134	#pagebreak()
135	== Exercise 4-2: Sequence Detection
136
137	#pagebreak()
138	= Document source code:
139	#separator()
140	#raw(read("sheet04_665250_664237.typ"), block: true, lang: "typ")
141
142