Login
jan

jan / TUHH - Computer Engineering - Sheet 04

Last active 7 minutes ago

Like 0

Mandatory Homework Sheet 04 for the Computer Engineering course at TUHH

Jan Meyer revised this gist 7 minutes ago · 05dac79

1 file changed, 111 insertions, 4 deletions

sheet04_665250_664237.typ
@@ -6,11 +6,13 @@
6 6
7 7 // helper function, full width sepearator with two newlines
8 8 #let separator() = [
9 - #line(stroke: 0.5pt + black, length: 100%)
10 9 \
10 + #line(stroke: 0.5pt + black, length: 100%)
11 11 \
12 12 ]
13 13
14 + #let framed(body) = box(stroke: 1pt, inset: 6pt, body)
15 +
14 16 = Computer Engineering - Sheet 04
15 17 \
16 18 #underline("Group Members:") \
@@ -22,13 +24,118 @@ This document was created using #link("https://typst.app", "typst").
22 24 The original typst file can be found
23 25 #link("https://gist.jnmr.dev/jan/CompEngSheet04", "here") \;
24 26 a copy of the documents source code has been appended to the end of the PDF.\
25 - No AI / LLM was used for the content of the answers. \
26 - \
27 + No AI / LLM was used for the content of the answers.
28 +
27 29 #separator()
30 +
28 31 == Exercise 4-1: Types of Automata
29 - == Exercise 4-2: Sequence Detection
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 +
30 133
31 134 #pagebreak()
135 + == Exercise 4-2: Sequence Detection
32 136
137 + #pagebreak()
138 + = Document source code:
139 + #separator()
33 140 #raw(read("sheet04_665250_664237.typ"), block: true, lang: "typ")
34 141

Jan Meyer revised this gist 23 hours ago · 3043dac

1 file changed, 34 insertions

sheet04_665250_664237.typ (file created)
@@ -0,0 +1,34 @@
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 + #line(stroke: 0.5pt + black, length: 100%)
10 + \
11 + \
12 + ]
13 +
14 + = Computer Engineering - Sheet 04
15 + \
16 + #underline("Group Members:") \
17 + Jan Meyer: `664237` \
18 + Luke Ethe: `665250` \
19 + \
20 + #underline("Information about this document:") \
21 + This document was created using #link("https://typst.app", "typst").
22 + The original typst file can be found
23 + #link("https://gist.jnmr.dev/jan/CompEngSheet04", "here") \;
24 + a copy of the documents source code has been appended to the end of the PDF.\
25 + No AI / LLM was used for the content of the answers. \
26 + \
27 + #separator()
28 + == Exercise 4-1: Types of Automata
29 + == Exercise 4-2: Sequence Detection
30 +
31 + #pagebreak()
32 +
33 + #raw(read("sheet04_665250_664237.typ"), block: true, lang: "typ")
34 +