Info

Wenn Sie Automaten angeben, tun Sie dies immer in Form eines Zustandsgraphen. Andere Formen der Darstellung (z.B. als Liste von Übergängen) werden nicht gewertet, da sie sehr viel aufwändiger zu korrigieren sind. Vergessen Sie nicht, im Zustandsgraph Start- und Endzustände zu markieren.

FSK2-1 Grammatik und Elimination von ε-Produktionen (2 Punkte)

a) Geben Sie kontextfreie Grammatiken (ggf. mit ε-Produktionen) an, die folgende Sprachen über dem Alphabet Σ = {a, b} erkennen:

i)

  • Alphabet:
  • 4-Tupel Grammatikform

i)

  • Alphabet:
  • 4-Tupel Grammatikform

Erste Idee

Zweite Idee (Besser?)

b) Betrachten Sie die Grammatik mit Produktionen

Aufgabenstellung

Geben Sie eine zu äquivalente Grammatik ohne ε-Produktionen an. Verwenden Sie den Algorithmus zur Elimination von ε-Produktionen aus der Vorlesung und geben Sie die Zwischenschritte Ihrer Berechnung an. (Das ermöglicht uns, Ihnen bei kleinen Fehlern noch Teilpunkte zu geben.)

Ziel: eliminieren

1. Schritt (ausfindig machen was bildet)

2. Schritt (-freie Grammatik bilden — entfernen)

3. Schritt (-kompensieren)

fehlt muss noch hinzugefügt werden

FSK2-2 DFAs und Minimierung (2 Punkte)

a) Geben Sie DFAs an, die folgende Sprachen über dem Alphabet Σ = {a, b} erkennen:

i)

flowchart LR
	id1(( )) --> id2((z0))
	id2((z0)) --a,b--> id3((z1))
	id3((z1)) --a--> id5(((z2)))
	id3((z1)) --a,b--> id2((z0))
	id5(((z2))) --a,b--> id6(((z3)))
	id6(((z3))) --a,b--> id5(((z2)))

Falsch siehe Lösung

Erklärung des Gedankenganges, warum so dargestellt:

  • Pfade zwischen und stellen dar, was eine Kette von Buchstaben vor ist
  • Der Pfad von zu stellt dar, was immer steht
  • ist ein akzeptierender Zustand, da und auf das das leere Wort folgen kann
  • Es kann aber auch eine Zeichenkette nach kommen, was mit den Pfaden zwischen und dargestellt wird
  • ist ein Endzustand, für alle ungerade Anzahlen von Buchstaben nach

ii)

flowchart LR
	id0(( )) --> id1((z0))
	id1((z0)) --a--> id2((z1))
	id2((z1)) --a--> id3((z2))
	id3((z2)) --a--> id4((z3))
	id4((z3)) --a,b--> id3((z2))
	id3((z2)) --b-->id5((z4))
	id5((z4)) --a,b--> id3((z2))
	id4((z3)) --b--> id6((z5))
	id5((z4)) --b--> id6((z5))
	id6((z5)) --b--> id7(((z6)))

und landen im Müllzustand

Erklärung des Gedankenganges, warum so dargestellt:

  • Pfade von bis stellt im Wort da
  • Pfade zwischen und stellen das Wort dar
  • Die Pfade ab und bis stellen das nach dem dar
  • ist ein akzeptierender Zustand, da das Wort ab da immer garantiert mit

b) Minimieren Sie die folgenden DFAs. Verwenden Sie die tabellarische Variante des Algorithmus zur Minimierung von DFAs aus der Vorlesung (nicht die grafische Variante und nicht den Algorithmus von letztem Jahr!). Geben Sie die Partitionstabelle und den minimalen DFA an.

i) DFA A1 über dem Alphabet :

graph LR
	id1(( )) --> circleId0(("`z0`"))
    circleId0(("`z0`")) -->|a| circleId1(("`z1`"))

    circleId1(("`z1`")) -->|a| circleId2(("`z2`"))

    circleId2(("`z2`")) -->|a| doubleCircleId3((("`z3`")))

    doubleCircleId3((("`z3`"))) -->|a| circleId4(("`z4`"))

    circleId4(("`z4`")) -->|a| circleId5(("`z5`"))

    circleId5(("`z5`")) -->|a| circleId6(("`z6`"))

    circleId6(("`z6`")) -->|a| doubleCircleId7((("`z7`")))

    doubleCircleId7((("`z7`"))) -->|a| circleId0(("`z0`"))
  • Endzustände und werden getrennt
  • und führen in Klasse 2 bzw. in andere Partition, deswegen teilen wird diese
  • Jetzt führen aber und auch in andere Partitionen und müssen geteilt werden
---
title: Graphische Darstellung der Partitionen
---
graph LR
    id1(( )) --> circleId0(("`P0`"))
    circleId0(("`P0`")) -->|a| circleId1(("`P1`"))
    circleId1(("`P1`")) -->|a| circleId2(("`P2`"))
    circleId2(("`P2`")) -->|a| doubleCircleId3((("`P3`")))
    doubleCircleId3((("`P3`"))) -->|a| circleId0(("`P0`"))

ii) DFA A2 aber dem Alphabet (bekannt aus der Vorlesung)

Graph aus Blatt entnehmen

Müllzustand fehlt muss als nicht Endzustand behandelt werden und müssen noch partitioniert werden, da sie in eine andere Partition führen, da jeweil 2 Pfeile von diesen Zuständen ausgehen, einmal auf sich selbst und einmal auf einen anderen Zustand

  • Endzustände
  • und führen in andere Partition werden deswegen getrennt
  • führt in 2 andere Partition deswegen trennen

FSK2-3 Kleine Automaten (0 Punkte)

a) Sei ein DFA mit Alphabet und genau einem Zustand. Zeigen oder widerlegen Sie: Es ist entweder oder .

Gedankengang:

  • Wenn das DFA nur einen Zustand hat, kann dieser entweder akzeptieren sein oder nicht

Beweis:

  • Es gibt 2 Fälle für :
    • Der Zustand von ist ein akzeptierender Zustand
    • Der Zustand von ist kein akzeptierender Zustand
  • Der Zustand von sei deklariert als
  • Alle Pfade von führen zurück zu
  • Erster Fall: akzeptierender Zustand
graph LR
id0(( )) --> id1(((z0))) --w∈Σ--> id1(((z0)))
  • Da der akzeptierende Zustand ist, kann man damit alle Wörter aus darstellen

    • Beim Lesen von jedem String landet der Automat in was ein akzeptierender Zustand ist
    • Es gilt also:
  • Zweiter Fall: nicht akzeptierender Zustand

graph LR
id0(( )) --> id1((z0)) --w∈Σ--> id1((z0))
  • Da kein akzeptierender Zustand ist, landet der Automat beim lesen in keinen akzeptierenden Zustand, was dazu führt, dass kein Wort gültig ist
    • Es gilt also:
    Schlussfolgerung: Die Behauptung ist wahr. Für einen DFA mit genau einem Zustand ist die von ihm akzeptierte Sprache entweder oder , abhängig davon, ob der einzige Zustand ein akzeptierender Zustand ist oder nicht.

b) Sei ein DFA mit Alphabet und genau zwei Zuständen. Angenommen es gibt ein Wort und für alle ist . Zeigen oder widerlegen Sie: Für jeden solchen Automaten ist .

Widerleg durch Gegenbeispiel

graph LR
id0(( )) --> id1((z1))
id1((z1)) --a,b--> id2(((z2)))
id2((z2)) --a,b--> id2(((z2)))

Dieser Automat kann das Wort Produzieren und besteht aus genau zwei Zuständen. Also gilt

c) Zeigen Sie: Für jeden DFA mit Alphabet und genau vier Zuständen gilt: Wenn für jede natürliche Zahl das Wort in ist, dann ist auch .

Erster Ansatz Induktion

Beweis durch Induktion: Induktionsanfang: Es wird bewiesen, dass die Aussage für die kleinste Zahl, den Startwert, gilt.

Indutktionsannahme: Gilt die Aussage für eine beliebige Zahl, so gilt sie auch für deren Nachfolge

Induktionsschritt:

Da nach der Induktionsannahme wahr ist, und weil eine korrekte Anwendung der Potenzgesetze ist, ist auch wahr.

Zusammenfassung: Durch den Induktionsanfang und den Induktionsschritt haben wir gezeigt, dass für alle natürlichen Zahlen gilt, beginnend bei . Somit gilt die Aussage auch für

FSK2-4 Grammatik-Konkatenation (0 Punkte)

  • FSK 2-4 verstehen was abgeht [completion:: 2024-07-15]

Aufgabenstellung

Seien und Typ-i-Grammatiken (für ), sodass und . Zeigen oder widerlegen Sie für alle : Es gibt eine Grammatik vom Typ , sodass .

Die Aufgabenstellung erfordert den Nachweis, dass für jede Typ-i-Grammatik (wobei ) und , die nicht enthalten, eine entsprechende Grammatik existiert, deren Sprache der Konkatenation der Sprachen von und entspricht, also .

Typ-0 (Rekursiv aufzählbare Grammatiken):

  • Typ-0-Grammatiken können jede berechenbare Sprache generieren, einschließlich der Konkatenation zweier Sprachen. Dies wird erreicht, indem die Produktionen von mit denen von kombiniert werden, wobei das Ende der Produktionen von direkt zum Beginn der Produktionen von übergeht.

Typ-1 (Kontextsensitive Grammatiken):

  • Für Typ-1-Grammatiken kann eine Grammatik konstruiert werden, die zuerst ein Wort aus und dann aus erzeugt, ohne die Kontextsensitivität zu verletzen.

Typ-2 (Kontextfreie Grammatiken):

  • Die Konstruktion von für kontextfreie Grammatiken umfasst die Einführung eines neuen Startsymbols und Regeln, die zuerst ein Wort aus und anschließend aus generieren.

Typ-3 (Reguläre Grammatiken):

  • Reguläre Grammatiken unterstützen die Konkatenation, indem das Endsymbol der Regeln von , das sonst auf das leere Wort führt, durch das Startsymbol von ersetzt wird.

Zusammengefasst ist es für alle Grammatiktypen möglich, die Konkatenation ihrer Sprachen durch eine Grammatik des gleichen Typs zu realisieren.