Universit¨ at Heidelberg Institut f¨ ur Informatik PD Dr. Wolfgang Merkle 3. November 2014 ¨ Ubungen zur Vorlesung Formale Sprachen und Automatentheorie Blatt 3 Aufgabe 1 (6 Punkte) Die Sprache L = {w ∈ {0, 1}∗ : #0 (w) > #1 (w)} ist nicht regul¨ar. (a) Zeigen Sie dies mit Hilfe des Pumping-Lemmas. (b) Zeigen Sie dies dadurch, dass Sie beweisen, dass der Index der Relation ∼L unendlich ist. Aufgabe 2 (4 Punkte) ¨ Die regul¨ aren Sprachen sind genau die Sprachen, die sich als Vereinigung von Aquivalenzklassen von Rechtskongruenzen mit endlichem Index darstellen lassen. Kann man diese Charakterisierung wie folgt ver¨ andern? ¨ (a) Statt Rechtskongruenzen mit endlichem Index betrachtet man beliebige Aquivalenzrelationen mit endlichem Index. ¨ (b) Statt der Vereinigung von Aquivalenzklassen von Rechtskongruenzen mit endlichem Index betrachtet ¨ man die Vereinigung von endlich vielen Aquivalenzklassen von Rechtskongruenzen mit beliebigem Index. Begr¨ unden Sie Ihre Antwort. Geben Sie gegebenenfalls ein Gegenbeispiel an. Aufgabe 3 (4 Punkte) Sei D = (Q, Σ, δ, q, F ) ein deterministischer endlicher Automat. Zwei Zust¨ande q1 , q2 aus Q heißen Daquivalent, kurz: q1 ∼D q2 , falls f¨ ur alle W¨orter u u ¨ ¨ber Σ gilt, dass δ(q1 , u) genau dann in F liegt, wenn δ(q2 , u) in F liegt. Beweisen Sie die beiden folgenden Aussagen. ¨ (a) Die Relation ∼D ist eine Aquivalenzrelation auf Q. (b) F¨ ur alle Zust¨ ande q1 , q2 aus Q mit q1 ∼D q2 und alle W¨orter u u ¨ber Σ gilt δ(q1 , u) ∼D δ(q2 , u). Aufgabe 4 (4 Punkte) Es sei L eine regul¨ are Sprache und es sei D = (Q, Σ, δ, q, F ) ein deterministischer endlicher Automat, der L erkennt. Beschreiben Sie umgangssprachlich die Arbeitsweise eines endlichen Automaten D , der die wie folgt definierte Sprache L erkennt L = {v ∈ Σ∗ : vvv ∈ L} . Abgabe: Bis Montag, den 10. November 2014, 14 Uhr. F¨ ur die Abgabe k¨ onnen Sie die K¨ asten im Erdgeschoss des Geb¨audes INF 294 (Angewandte Mathematik) ¨ benutzen. Die Ubungsbl¨ atter sind im PDF-Format abrufbar unter http://math.uni-heidelberg.de/logic/ws14/formsprach ws14.html .