TU Ilmenau, Fachgebiet Automaten und Logik Prof. Dr. Dietrich Kuske, Martin Huschenbett, Roy Mennicke Besprechung am 23.10. bzw. 24.10. ¨ Automaten, Sprachen und Komplexit¨ at, Ubungsblatt 1 (1) Entscheiden Sie f¨ ur jede der folgenden Mengen, ob sie eine formale Sprache ist. (a) alle deutschen St¨ adte (d) alle geraden Primzahlen echt gr¨oßer 2, (b) die Namen der Einwohner Pekings (e) die Dezimaldarstellungen nat. Zahlen (c) alle nat¨ urlichen Zahlen (f) die Dezimaldarstellungen reeller Zahlen (2) Sei Σ = {a, b, c}. Unter den folgenden 16 Sprachen u ¨ber Σ befinden sich acht Paare gleicher Sprachen. Finden Sie heraus, welche Paare das sind und geben Sie jeweils eine kurze Begr¨ undung f¨ ur die entsprechende Gleichheit. L1 = {w ∈ Σ∗ | |w|a = |w|b } L9 = L31 L2 = {w ∈ Σ∗ | |w|a = 0} L10 = (L2 L3 )2 L3 = {w ∈ Σ∗ | |w|a = 2} L11 = Σ∗ \ L2 ∗ L4 = {w ∈ Σ | |w|a = 4} L12 = {an bn | n ∈ N} L5 = {w ∈ Σ∗ | |w|a = |w|b = |w|c } L13 = {ab}+ L6 = {b, c}∗ {a}{b, c}∗ {a}{b, c}∗ L14 = {b, c}∗ L7 = L1 ∩ {w ∈ Σ∗ | |w|b = |w|c } L15 = Σ∗ {a}Σ∗ L8 = L1 ∩ {a}∗ {b}∗ L16 = {a}{ba}∗ {b} (3) Sei Σ ein beliebiges Alphabet. Zeigen Sie, dass Σ∗ abz¨ahlbar ist. (4) Im Folgenden sind vier Grammatiken durch die Liste ihrer Produktionen gegeben. Dabei ist S jeweils die Startvariable, S, A und B sind Variablen und a und b sind Terminale. G1 : S → AA | ε, A → B, B→b G2 : S → aA, A → aA | ε, B → bA G3 : S → AB | ε, G4 : S → aAS | ε, A → S | AA | a, B→b aA → aaB, aB → ab Bearbeiten Sie die folgenden Teilaufgaben f¨ ur jedes i ∈ {1, 2, 3, 4}. (a) Nennen Sie zwei W¨ orter, die in L(Gi ) liegen. Geben Sie f¨ ur beide W¨orter jeweils eine Ableitung in Gi an. (b) Geben Sie an, welche der folgenden Eigenschaften Gi besitzt: kontextsensitiv, kontextfrei und rechtslinear. (5) Bearbeiten Sie die folgenden Teilaufgaben: (a) Sei G die kontextfreie Grammatik mit Startvariable S und den folgenden Produktionen: S → aAC A → Bb B → aA | ε C → CC | c Welche Sprache wird von G erzeugt? Konstruieren Sie mittels des Verfahrens aus dem Beweis des Lemmas auf Folie 49 eine kontextsensitive Grammatik G mit L(G) = L(G ). (b) Seien Σ = {0, 1} und w = a1 a2 . . . an ein Wort mit n ∈ N und ai ∈ Σ f¨ ur alle 1 ≤ i ≤ n. Mit wR bezeichnen wir im Folgenden das Spiegelwort an an−1 . . . a1 von w. Geben Sie eine kontextfreie Grammatik G u ¨ber dem Alphabet Γ = Σ ∪ {#} an, so dass gilt: L(G) = {v#w ∈ Σ∗ {#}Σ∗ | wR ist Pr¨afix von v} (6) Sei Gi = (Vi , Σ, Si , Pi ) eine kontextfreie Grammatik f¨ ur i ∈ {1, 2}. Konstruieren Sie Grammatiken G∪ , G• und G∗ , so dass gilt: L(G∪ ) = L(G1 ) ∪ L(G2 ) L(G• ) = L(G1 ) · L(G2 ) L(G∗ ) = L(G1 )∗ Begr¨ unden Sie jeweils kurz informal, warum Ihre Grammatik die korrekte Sprache erzeugt. Aufgaben zum Selbststudium (nicht bewertet) (7) Bearbeiten Sie die folgenden Teilaufgaben: (a) Es seien Σ ein Alphabet und L ⊆ Σ∗ eine Sprache. Zeigen Sie, dass L∗ = (L∗ )2 gilt. Gilt die Gleichung auch, wenn man den Kleene-Stern ∗ durch + ersetzt? (b) Geben Sie ein Alphabet Σ und Sprachen K0 , K1 , K2 , . . . ⊆ Σ∗ an, so dass f¨ ur jedes n ∈ N die Sprache Kn n-elementig ist und Kn2 m¨oglichst wenige W¨orter enth¨alt. (c) Geben Sie ein Alphabet Σ und Sprachen L0 , L1 , L2 , . . . ⊆ Σ∗ an, so dass f¨ ur jedes n ∈ N die Sprache Ln n-elementig ist und L2n m¨oglichst viele W¨orter enth¨alt. (8) Geben Sie einen Algorithmus an, der, bei Eingabe einer kontextfreien Grammatik G, die Menge aller nilpotenten Variablen von G ausgibt. Wenden Sie Ihren Algorithmus anschließend auf die folgende Grammatik mit Startvariable S an: S → AC A → aA | C B → Cb | BB C → AB | ε (9) Geben Sie eine kontextfreie Grammatik G u ¨ber dem Alphabet Σ = {a, b} an, so dass gilt: L(G) = {w ∈ Σ∗ | |w|a = |w|b } 2