Dr. Ingmar Meinecke SS 2010 Institut für Informatik [email protected] http://www.informatik.uni-leipzig.de/∼meinecke/ Tel. 97-32172 Übungsblatt zur Vorlesung Automatentheorie“ ” 4. Serie • Die mit “H” gekennzeichneten Aufgaben sind schriftliche Hausaufgaben und direkt vor der Vorlesung am Dienstag in einer Woche abzugeben. • Die mit “S” gekennzeichneten Aufgaben sind bis zur Übung vorzubereiten und dort vorzustellen. H 4-1. (a) Untersuchen Sie die folgenden Mengen in den jeweiligen Monoiden auf Erkennbarkeit: – {(abn , cn ) | n ∈ } im Monoid {a, b}∗ × c∗ mit der komponentenweisen Konkatenation, – {1} im Monoid ( , +), – {n ∈ | n ≤ 3 ∨ n ≥ 6} im Monoid ( , max). Beweisen Sie Ihre Aussagen. (b) Sei A = {a, b, c}. Finden Sie endliche Monoide M1 , M2 und M3 sowie Homomorphismen hi : A∗ → Mi für i = 1, 2, 3, so dass hi die Sprache Li erkennt, wobei L1 = cA∗ , L2 = (A∗ aaA∗ )C und L3 = L1 ∩ L2 . Dabei wird L von h erkannt, falls L = h−1 (h(L)). S 4-2. Finden Sie zwei verschiedene Monoide M und N mit jeweils drei Elementen und geben Sie jeweils eine nichttriviale Sprache über dem Alphabet A = {a, b} an, die von einem Homomorphismus nach M bzw. N erkannt werden kann. S 4-3. Seien L1 und L2 zwei erkennbare Sprachen in einem Monoid M . (a) Die Sprache Li werde vom Homomorphismus hi : M → Ni in das endliche Monoid Ni (i = 1, 2) erkannt. Finden Sie geeignete endliche Monoide und Homomorphismen, die jeweils LC 1 , L1 ∪ L2 und L1 ∩ L2 erkennen. (b) Die Sprache Li werde vom M -Automaten Ai (i = 1, 2) erkannt. Finden Sie M Automaten, die jeweils LC 1 , L1 ∪ L2 und L1 ∩ L2 erkennen. Termine: • Abgabe der Hausaufgaben direkt vor der Vorlesung am Dienstag, 11.05.10 • Besprechung der Seminaraufgaben in der Woche vom 10. – 14.05.10 Achtung! In der Woche vom 3. bis zum 7. Mai fallen sowohl die Vorlesungen wie die Übungen Automatentheorie“ aus. ”
© Copyright 2024 ExpyDoc
