FGI-1 – Formale Grundlagen der Informatik I

FGI-1 – Formale Grundlagen der Informatik I
Logik, Automaten und Formale Sprachen
Aufgabenblatt 2 : DFAs, NFAs und andere Automaten
Präsenzteil am 12.-15. April – Abgabe am 19.-22. April 2016
Präsenzaufgabe 2.1: Geben Sie einen DFA A an, der die Sprache L all jener Worte w ∈ {0, 1}∗
akzeptiert, bei denen die Anzahl der 0en durch 3 und die Anzahl der 1en durch 2 teilbar ist (jeweils
ohne Rest, d.h. ein Wort w soll genau dann akzeptiert werden, wenn |w|0 ein Vielfaches von 3 und
|w|1 ein Vielfaches von 2 ist).
Zeigen Sie, dass Ihr Automat das Gewünschte leistet, indem Sie zwei Mengeninklusionen beweisen.
Präsenzaufgabe 2.2:
Gegeben sei der folgende NFA A:
0,1
/ z0
0
/ z1
1
/ z2
1. Welche Sprache akzeptiert dieser NFA (ohne Beweis)?
2. Geben Sie alle Rechnung von A auf dem Wort 01101 an. Geben sie zudem die Menge der
nach jedem Buchstaben erreichten Zustände an (also formal die Menge δ̂(z0 , v) für jedes
Präfix v von 01101).
3. Konstruieren Sie mittels der Potenzautomatenkonstruktion einen DFA B mit L(B) = L(A)
(d.h. einen äquivalenten DFA).
Übungsaufgabe 2.3: Geben Sie einen DFA an, der alle Zeichenketten über dem Alphabet {0, 1}
akzeptiert, die 101 als Teilwort enthalten. Bspw. soll also 11010 akzeptiert werden, da 101 vom
zweiten bis vierten Buchstaben auftritt.
von
4
Zeigen Sie insbesondere, dass Ihr Automat das Gewünschte leistet, indem Sie zwei Mengeninklusionen beweisen.
Übungsaufgabe 2.4:
Gegeben sei der folgende NFA A:
von
4
0,1
/ z0
0
5 z1
1
(
4 z2
1
1. Welche Sprache akzeptiert dieser NFA? Beweisen Sie Ihre Behauptung!
2. Konstruieren Sie mittels der Potenzautomatenkonstruktion einen DFA B mit L(B) = L(A)
(d.h. einen äquivalenten DFA).
Übungsaufgabe 2.5: Erweitern Sie die Definition des DFA so, dass der DFA nun zwei Leseköpfe
hat, also an zwei Stellen auf dem Band lesen kann. Zu Beginn sollen beide Leseköpfe ganz links auf
dem Eingabeband stehen (also auf dem ersten Symbol des Eingabewortes; oder im Spezialfall des
leeren Wortes auf einem leeren Feld). Dann sollen sie sich aber unabhängig voneinander bewegen
können. Überlegen Sie sich zunächst, wie Sie die Überführungsfunktion anpassen müssen. Welche
weiteren Dinge (Zustände, Startzustand, Endzustände, erweiterte Überführungsfunktion, akzeptierte Sprache) müssen angepasst werden? Beschreiben und begründen Sie Ihre Anpassungen.
Hinweis: In dieser Aufgabe sollen Sie das Vokabular der Mathematik benutzen, um Dinge zu beschreiben. Betrachten Sie zur Übung noch einmal, wie wir vom DFA zum NFA gelangten, was wir
ausdrücken wollten und was wir bei der Definition dazu angepasst haben. Dann betrachten Sie obige Fragestellung und überlegen Sie sich, was man anpassen muss und wie dies geschehen könnte.
Wichtig ist insb. auch, dass Ihre Gedanken vom Leser nachvollzogen werden können, achten Sie
also auf eine gute Beschreibung Ihrer Anpassungen. Beachten Sie auch, von welchen “weiteren
Dingen” oben die Rede ist und von welchen nicht. Sie können auch z.B. die Konfiguration anpassen. Dies ist aber gar nicht zwingend nötig. Beachten Sie auch, dass die Aufgabenstellung nicht
erschöpfend ist und Ihnen noch Freiheiten bei der genauen Definition lässt. Um so wichtiger ist
es, dass Sie beschreiben, was Sie mit ihren Definitionen erreichen wollen.
Informationen und Unterlagen zur Veranstaltung unter:
http://www.informatik.uni-hamburg.de/TGI/lehre/vl/SS16/FGI1
Version vom 9. April 2016
Bisher erreichbare Punktzahl :
24
von
4

Download Report