Link zur Web Version:https://www.notion.so/AB2-53ebe76b45bf4af9b8f4d4c1d23d4946

Aufgabe 1

$\sum$ Alphabet, nicht leere endliche Menge an Symbolen

$\varepsilon$ Leerwort (equivalent zum Leer-String ≠ Leerzeichen$␣$≠ leere Menge )

$w$ Wort über $\Sigma$ , endliche Verkettung von Symbolen

Verkettung: $w \cdot w' = ww'$

Wort Mengen

$L$- Formale Sprache über$\sum^*$

Angabe

$\sum = \{\texttt{d,e,n,o,s}\}$

Die formale Sprache über $\sum^*$ :

a) Posix Extended Regular Expression

$\texttt{L = \^{} [denos]* (sonne | sonde) \$}$

b) Nicht deterministischer Automat

Die Korrektheit der Modellierung ist unmittelbar einsichtig.

c) Determinisierung

Gegeben: NEA

Gesucht: DEA

Definition von DEA$\mathcal{\widehat{A}}$

Dadurch, dass es keine$\varepsilon$gibt ist Tabelle von$\delta$gleich mit$\delta^*$

Anfangszustand ist $1$ , Endzustand ist $6$ .

$\begin{array}{c|ccccc}\delta^{*} & \mathrm{d} & \mathrm{e} & \mathrm{n} & \mathrm{o} & \mathrm{s} \\\hline 1 & \{1\} & \{1\} & \{1\} & \{1\} & \{1,2\} \\2 & \{\} & \{\} & \{\} & \{3\} & \{\} \\3 & \{\} & \{\} & \{4\} & \{\} & \{\} \\4 & \{6\} & \{\} & \{5\} & \{\} & \{\} \\5 & \{\} & \{7\} & \{\} & \{\} & \{\} \\6 & \{\} & \{7\} & \{\} & \{\} & \{\} \\7 & \{7\} & \{7\} & \{7\} & \{7\} & \{7\}\end{array}$

Wir definieren eine $\widehat{\delta}$

Anfangszustand ist $1$ , Endzustand ist jeder Block der mit $1$ anfängt und mit $7$ endet.

$\begin{array}{c|ccccc}\widehat{\delta} & \mathrm{d} & \mathrm{e} & \mathrm{n} & \mathrm{o} & \mathrm{s} \\\hline\{1\} & \{1\} & \{1\} & \{1\} & \{1\} & \{1,2\} \\\{1,2\} & \{1\} & \{1\} & \{1\} & \{1,3\} & \{1\} \\\{1,3\} & \{1\} & \{1\} & \{1,4\} & \{1\} & \{1\} \\\{1,4\} & \{1,6\} & \{1\} & \{1,5\} & \{1\} & \{1\} \\\{1,5\} & \{1\} & \{1,7\} & \{1\} & \{1\} & \{1\} \\\{1,6\} & \{1\} & \{1,7\} & \{1\} & \{1\} & \{1\} \\\{1,7\} & \{1,7\} & \{1,7\} & \{1,7\} & \{1,7\} & \{1,7\} \end{array}$

$\widehat{F}=\{\{1, 7\}\}$

$\widehat{Q}=\{\{1\},\{1,2\},\{1,3\},\{1,4\},\{1,5\},\{1,6\},\{1,7\}\}$

Aufgabe 2

Algebraische Notation $\rarr$ Endliche Automaten

Um Klammern auszulassen - Stärke der Bindung:

a)

$ab^*b+(ba)^* = (a(b^*)b)+((ba)^*)$

b)

$(a +cb^*)cc^* = (a + c(b^*))c(c^*)$

Aufgabe 3

Sind diese Gleichungen gültig?

a)

$L \cdot\{\}=L \cup\{\varepsilon\}$

Nein. denn das die Leere Menge ist das Nullelement bezüglich der Verkettung $(\forall L: ~~L \cdot\{\}=\{\})$ während die Vereinigung mit dem Leerwort die Gruppe um das Leerwort erweitert.

Gegenbeispiel:

b)

$L \cdot\{\varepsilon\}=L \cup\{\}$

Ja! Denn $\{\varepsilon\}$ ist das Einselement bezüglich der Verkettung $(\forall L: ~~L \cdot\{\varepsilon\}=L)$ und die leere Menge $\{\}$ ebenso in bezug auf die Vereinigung $(\forall L: ~~L \cup\{\}=L)$ .

c)

$\{\varepsilon\} \cdot L^{*}=L^{+}$

Zuerst sei aus Unterbeispiel b) festgehalten, dass diese Gleichung gleichzusetzen ist mit:

$L^{*}=L^{+}$

Und der Definition zufolge:

Also kann diese Gleichung nicht stimmen.

Gegenbeispiel (aus der Vorlesung):

d)

$(L \cdot L)^{*}=L^{*} \cdot L^{*}$

Wir formen diese Gleichungen um:

Wir wissen weiters, dass:

Daraus folgt:

Daraus wird offensichtlich:

Gegenbeispiel:

Aufgabe 4

Gegeben:

Suche: Automat $\mathcal A$ mit der Eigenschaft:

Die Zustände und die jeweiligen Bezeichnungen dafür sind irrelevant, wichtig ist dass man für die gleichen Wörter zum Endzustand kommt.

Wir führen eine neue Notation ein:

Definition:

$\mathcal{A}=\left\langle Q, \Sigma, \delta, q_{0}, F\right\rangle$

Angenommen $Q_1 = \{q_{1,0},q_{1,1},q_{1,2},\dots,q_{1,n_1}\} \quad Q_2 = \{q_{2,0},q_{2,1},q_{2,2},\dots,q_{2,n_2}\}$

$Q = \{q_{1, j}q_{1,k} \mid j = [0;n_1], ~~k = [0;n_2] \} \cup \text{trap}$

(jede mögliche Kombination an Zuständen soll möglich sein + Falle)

$q_{0} = i_1i_2 \in Q$

Angenommen $F_1 = \{f_{1,0},f_{1,1},f_{1,2},\dots,f_{1,n_1}\} \quad F_2 = \{f_{2,0},f_{2,1},f_{2,2},\dots,f_{2,n_2}\}$

Dann $F = \{f_{0,j}f_{1,k} \mid j = [0;n_1], ~~k = [0;n_2]\}$

Erweiterte Übergangsfunktion (auch für Leerwort)

Idee: Wenn es vom Eingabezustand und Eingabebuchstaben in beiden Automaten $\mathcal A_1$ und $\mathcal A_2$ einen Weg zum Ziel gibt, dann weise zum nächsten Zustand, ansonsten zur Falle.

$\delta^*: Q \times \Sigma^* \mapsto Q$

$\forall q_1 \in Q_1, q_2 \in Q_2, s \in \Sigma, w \in \Sigma^{*}:$

Akzeptierte / Generierte Sprache

Aufgabe 5

Ziel: Automat $\rarr$ endlicher Automat der dafür geeignet ist $\rarr$ Regulärer Ausdruck

Regeln

Problem: Unser Anfangszustand ist ein Endzustand und wir haben mehrere Endzustände.

Geeignetes Automat

Algorithmus

Für jeden Zustand $q \in Q-\{i, f\}$ :

1. Füge zwischen allen Nachbarn $p, p'$ von $q$ neue Übergänge hinzu mit regulären Ausdrücken beschriftet

2. Entferne $q$ und alle Kanten von und nach $q$ aus dem Automaten.

Resultat

Zustand $0$ :

Zustand $1$ :

Zustand $2$ :

Aufgabe 6

a) Algebraische Notation

$gruppe = I + II$

$kategorie= (1 +2+3 )(\varepsilon+(G+D))$

$ex= (\varepsilon+Ex)$

$großbuchstabe = (A+B+C+\dots+Z)$

$zündart = (a+b+c+\dots+z)((a+b+c+\dots+z)+großbuchstabe+(0+1+2+3+\dots+9))^*$

$exgr=IIgroßbuchstabe$

$klasse = T(1+2+\dots+6)$

$schild= gruppe␣kategorie␣ex␣zündart␣exgr␣klasse$

b) POSIX Notation

$\texttt{schild = \^{}(I|II)␣[1-3](G|D)?␣(Ex)?␣(a-z)[a-zA-Z0-9]*␣II[A-Z]␣T[1-6]\$}$

c) Syntaxdiagramm

schild:

Aufgabe 7

$G=\langle N, T, P, A\rangle$

$\begin{aligned}N=&\{A, B, C, D\} \\T=&\{\mathrm{h}, \mathrm{sch}, \mathrm{schu}, \mathrm{uhu}, \mathrm{uu}\} \\P=&\{A \rightarrow \operatorname{sch} \text { uhu } A \mid \text { uhu } \mid B,\\& B \rightarrow \text { h uhu } C \\& C \rightarrow \text { uhu } D \\&D \rightarrow \operatorname{schu} D|\mathrm{uu}| A\}\end{aligned}$

Von Grammatik$G$generierte Sprache

$\mathcal{L}(G)=\left\{w \in T^{*} \mid S \stackrel{*}{\Rightarrow} w\right\}$

Alle Wörter aus Terminal-Verknüpfungen bei denen ein Startsymbol nach Ableitung zu einem gültigen Wort führt.

Quasi Menge aller mit der Grammatik ableit-baren Wörter.

In diesem Fall muss jedes Wort entweder mit einem Terminal oder dem Nonterminal $A$ (Startsymbol) anfangen.

a)

$\texttt{h uhu uhu schu uu }$

$A \Rarr_P P(B)$

b)

$\texttt{sch uhu h uhu uhu schu schu sch uhu uhu }$

$A \Rarr_P \text{sch uhu } P(A)$

c)

$\texttt{sch uhu sch uhu uhu uu}$

$A \Rarr_P \text{sch uhu } P(A)$

Lösung:

$\texttt{sch uhu schu uhu uhu}$

d)

Das kürzeste Wort wäre ein Terminal mit der geringsten Buchstabenanzahl: $\text{h}$

e)

Diese Sprache ist regulär / lässt sich mit einem endlichen Automaten beschreiben, weil sie nicht beliebig tief schachtelbar ist (wie bei einem wohlgeformten Klammerausdruck).

$P=\{ \\A \rightarrow \operatorname{sch} \text { uhu } A \mid \text { uhu } \mid B, \\B \rightarrow \text { h uhu } C \\C \rightarrow \text { uhu } D \\D \rightarrow \operatorname{schu} D~|~\mathrm{uu}~|~ A \\\}$

Ist äquivalent zur Grammatik:

$P=\{ \\A \rightarrow \operatorname{sch} \text { uhu } A \mid \text { uhu } \mid \text { h uhu} \text { uhu } D, \\D \rightarrow \operatorname{schu } ~D~ | ~\mathrm{ uu }~| ~A \\\}$

Und lässt sich mit dem folgendem Automaten beschreiben:

Aufgabe 8

a) Als kontextfreie Grammatik (EBNF Notation)

Vorteile der BNF:

Vorteile der EBNF (verglichen zur BNF):

buchstabe =  "A" | "B" | "C" | "D" | "E" | "F" | "G"
| "H" | "I" | "J" | "K" | "L" | "M" | "N"
| "O" | "P" | "Q" | "R" | "S" | "T" | "U"
| "V" | "W" | "X" | "Y" | "Z" | kleinbuchstabekleinbuchstabe = "a" | "b" | "c" | "d" | "e" | "f" | "g"
| "h" | "i" | j" | "k" | "l" | "m" | "n"
| "o" | "p" | q" | "r" | "s" | "t" | "u"
| "v" | "w" | x" | "y" | "z"ordner = buchstabe {buchstabe} "[" [liste] "]"liste = "," datei | "," ordner | listedatei = dateiname "." dateiendungdateiname = buchstabe [buchstabe] [buchstabe] [buchstabe]dateiendung = kleinbuchstabe kleinbuchstabe [kleinbuchstabe]

b) Als regulärer Ausdruck (algebraische Notation)

$kleinbuchstabe = a+b+c+\dots+z$

$buchstabe = (kleinbuchstabe+ (A+B+C+\dots+Z))$

$ordner = buchstabe(buchstabe)^*[inhalt]$

$inhalt = \varepsilon + liste$

$liste= \varepsilon+,datei+,ordner+liste$

$dateiname= buchstabe (buchstabe+\varepsilon) (buchstabe+\varepsilon) (buchstabe+\varepsilon)$

$dateiendung = (kleinbuchstabe)(kleinbuchstabe)(kleinbuchstabe+\varepsilon)$

$datei = dateiname.dateiendung$

Aufgabe 9

a) Hakan kauft etwas.

$\mathcal{P}=\{\text{Hakan } /1,\text { Kauft } / 2\}$

Mögliche Modellierungen:

b) Hakan kauft eine DVD.

$\mathcal{P}=\{\text{Hakan } /1,\text { Kauft } / 2, \text { CD } / 1\}$

Mögliche Modellierungen:

c) Anna kauft alles das, was Hakan kauft.

$\mathcal{P}=\{\text{Hakan } /1,\text { Kauft } / 2, \text { Anna } / 1\}$

Mögliche Modellierung:

d) Jeder kauft etwas.

$\mathcal{P}=\{\text{Mensch } /1,\text { Kauft } / 2\}$

Mögliche Modellierung:

e) Jemand kauft alles.

$\mathcal{P}=\{\text{Mensch } /1,\text { Kauft } / 2\}$

Mögliche Modellierung:

Aufgabe 10

Universum, Prädikate, Funktionen

$\mathcal{U}=\{\text { Obi-Wan, Yoda, Luke, Anakin, DarthVader, DarthBane, DarthMaul, }\\\text { DarthTyrannus, DarthSidious, Yaddle\} }$

$\mathcal{P}=\{Bekämpft/2,~Jedi/1,~Sith/1,~Dunkel/1 \}$

$\mathcal{F}=\{\text {yoda}/ 0, ~\text{luke}/0, ~darthvader/0\}$

a)

Es gibt dunkle Sith, die alle Jedi-Ritter bekämpfen.

Mögliche Modellierungen:

b)

Kein Jedi-Ritter bekämft alle Sith.

Mögliche Modellierung:

Interpretationen

$I(J e d i)=\{\text { Obi-Wan, Yoda, Luke, DarthVader, Yaddle }\}$

$I( Sith )=\{\text { DarthVader, DarthBane, DarthMaul, DarthTyrannus\} }$

$I(Dunkel)=\{\text { DarthBane, DarthVader, Anakin }\}$

$\begin{aligned}I(Bekämpft)=~&\{(\text { Obi-Wan, DarthTyrannus), (Obi-Wan, DarthBane), (Obi-Wan, DarthMaul), }\\& \text { (Yoda, DarthMaul), (Yoda, DarthTyrannus), } \\&\text { (DarthVader, Luke), (DarthVader, DarthVader), } \\& \text { (Anakin, Obi-Wan), (Anakin, Luke), (Anakin, DarthVader), } \\&\text { (DarthBane, Obi-Wan), (DarthBane, Luke), (DarthBane, Yoda), } \\& \text { (DarthSidious, Yaddle)\} } \end{aligned}$$I(luke )=\text { Luke }$

$I({ darthvader })=\text { DarthVader }$

c)

$\exists x(\text {Dunkel }(x) \wedge \operatorname{Sith}(x) \wedge(\text { Bekämpft }(x, \text { luke }) \not \equiv \text { Bekämpft }(x, \text { darthvader })))$

Es gibt mindestens einen dunklen Sith der entweder Luke oder Darthvader bekämpft aber nicht beide gemeinsam.

Überprüfung dieser Aussage

d)

$\forall x \exists y(\operatorname{Jedi} (x) \wedge \operatorname{Sith}(y) \wedge \operatorname{Bekämpft}(x, y))$

Alle Jedis bekämpfen mindestens einen Sith.

Überprüfung dieser Aussage

e)

$\forall x(\operatorname{Jedi}(x) \supset \exists y(\operatorname{Sith}(y) \wedge \operatorname{Bekämpft}(y, x)))$

Alle Jedis werden von mindestens einem Sith bekämpft.

Überprüfung dieser Aussage

Aufgabe 11

Petri-Netz → endlicher Automat

Bezeichnungen der Transitionen $\{t_1, t_2, t_3, t_4\}$ = Alphabet $\Sigma$

Belegung einer Stelle mit einem Token = Zustand $Q$

$\mathcal{A}=\left\langle Q, \Sigma, \delta, q_{0}, F\right\rangle$finite automaton

$Q = \{210,101,111,110,002,010,012,011,021,020,030\}$all possible states (finite)

$\sum = \{t_1, t_2, t_3, t_4\}$input alphabet

$\delta: Q \times \Sigma \mapsto Q$transition function

$q_{0} = 210$initial state

$F = \{020,030\}$final states

Aufgabe 12

a)

Brücke für Fahrzeuge

2 Spuren, für 2 Richtungen - in beiden Richtungen befahrbar

Fahrzeugpositionen: $\{vorBrücke, aufBrücke, nachBrücke\}$

Anfangszustand: Alle Fahrzeuge möchten Brücke überqueren

Wir haben insgesamt 6 Stellen: $\{\ vorOben,~aufOben,~nachOben,~vorUnten,~aufUnten,~nachUnten\}$

b)

Nur 3 Fahrzeuge gleichzeitig auf der Brücke erlaubt, unabhängig von Fahrtrichtung.

Das entspricht einem Buffer mit 3 Tokens.

c) d)

Wenn eine Reperatur stattfindet:

Hinweis: diesmal habe ich die Stellen der Fahrzeug-Spuren im Modell vertauscht damit das Modellieren einfacher ist.

Es kommt auch zu keinen Kollisionen, dadurch, dass die Buffer der einzelnen Seiten unabhängig voneinander sind und eine Seite komplett leer sein muss bevor die Ampel schaltet.