FGI-1 – Formale Grundlagen der Informatik I
Logik, Automaten und Formale Sprachen
Aufgabenblatt 3 : Abschlusseigenschaften und Pumping Lemma
Präsenzteil am 19.-22. April – Abgabe am 26.-29. April 2016
Präsenzaufgabe 3.1: Geben Sie einen DFA A1 an, der die Sprache L all jener Worte w ∈ {0, 1}∗
akzeptiert, die auf 1 enden und einen DFA A2 , der jene Worte w ∈ {0, 1}∗ akzeptiert, die die
Zeichenkette 11 enthalten. (Begründen Sie kurz mündlich, warum Ihre Automaten das Gewünschte
leisten.)
Konstruieren Sie dann mittels der Konstruktion aus der Vorlesung den Produktautomaten von A1
und A2 .
Präsenzaufgabe 3.2:
Beweisen Sie mittels des Pumping Lemmas, dass die Sprache
L = {an bm | n < m}
nicht regulär ist.
Übungsaufgabe 3.3:
Betrachten Sie die beiden folgenden NFAs A und B:
0,1
(
u
0,1
0
(
/ v
w
0,1
0
/x
von
4
0,1
0
/ y
Bestimmen Sie zu den NFAs A und B mittels der Potenzautomatenkonstruktion aus der Vorlesung
jeweils einen DFA A0 bzw. B 0 mit L(A0 ) = L(A) und L(B 0 ) = L(B).
Wenden Sie dann auf A0 und B 0 die Produktautomatenkonstruktion aus der Vorlesung an und
bestimmen Sie so einen DFA C mit L(C) = L(A0 ) ∩ L(B 0 ).
Übungsaufgabe 3.4:
von
5
∗
1. Sei L ⊆ Σ eine reguläre Sprache und a ∈ Σ ein Symbol. Zeigen Sie, dass dann auch
L ← a := {w ∈ Σ∗ | w = va, v ∈ L}
eine reguläre Sprache ist.
(Hinweis: Überlegen Sie, welche Möglichkeiten wir kennen, um reguläre Sprachen darzustellen. Wählen Sie hiervor eine gute aus.)
2. Sei L ⊆ Σ∗ eine reguläre Sprache und a ∈ Σ ein Symbol. Zeigen Sie, dass dann auch
L ↓ a := {w ∈ Σ∗ | ∃v, u ∈ Σ∗ : w = vau und vu ∈ L}
regulär ist.
(Hinweis: Knifflig! Probieren Sie mit Kopien eines Automaten für L zu arbeiten.)
Übungsaufgabe 3.5:
Zeigen Sie mittels des Pumping Lemmas, dass die Sprache
von
3
∗
M := {w ∈ {0, 1} | |w|0 = 2 · |w|1 }
nicht regulär ist.
Informationen und Unterlagen zur Veranstaltung unter:
http://www.informatik.uni-hamburg.de/TGI/lehre/vl/SS16/FGI1
Version vom 18. April 2016
Bisher erreichbare Punktzahl :
36
© Copyright 2024 ExpyDoc
