Gibt es musterlösung
diese aufgabe
http://www.informatik.uni-hamburg.de/TGI/lehre/vl/SS03/F2/F2KV2003.pdf.gz ?
EDIT: Bitte vernünftige Titel wählen, danke.
tja, kann man doch selber basteln,
muss noch nicht unbedingt alles richtig sein,
dann bitte verbessern
1.
MR1 = die Menge der Wörter, die das Teilwort ab enthält
Beispiele: ab, abab
MR2 = die Menge der Wörter, bei denen nach einem c kein a mehr vorkommt
Beispiele: aac, abababcbb
Automat:
NFA aus 2 Teilautomaten für die beiden Bedingungen der Sprache:
Startzustände: Z1, Z3
Endzustände: Z2, Z3, Z4
a,b a,b
.--. .--.
v | v |
| |
.----. c .----.
||Z1 | -----> | Z2||
'----' '----'
b,c a
.--. .--.
v | v |
| |
.----. a .----.
||Z3|| -----> | Z4||
'----' <---- '----'
c
2.
Ein minimaler endlicher Automat ist ein endlicher Automat,
für dessen akzeptierte Sprache kein anderer endlich Automat
mit weniger Zuständen existiert.
(muss eventuell deterministisch und/ oder vollständig sein?,
steht bestimmt im Skript)
3.
(a)
BAC |><| CAD -> B < C
DBCD |><| ABCD -> D < A
DABC |><| DBCD -> A < B
-> D < A < B < C ist die lineare Ordnung
(b)
BAC |><| ABCD -> B < A
DABC |><| DBCD -> A < B
Widerspruch, also existert keine lineare Ordnung in diesem Fall
