Es gibt auf dieser Seite teilweise Fehler mit dem rendern von den LaTeX ausdrücken aufgrund der $ und # ich bitte um Entschuldigung während ich nach einer Lösung suche

Falls dieses Problem noch länger besteht, bitte einen Kommentar schreiben um mich daran zu erinnen

FSK6-1 Kontextfreie Grammatiken und Kellerautomaten (2 Punkte)

Aufgabenstellung:

Sei L = \{a^{2n}\a^n \mid n \in \mathbb{N}_{\gt0}}\Sigma = {a, .

a) Geben Sie eine kontextfreie Grammatik an, die erkennt.

Falsch, da nicht N>0

Korrekt

Gedankengang:

  • Links vom $ müssen doppelt so viele a’s stehen wie auf der rechten Seite.
  • bildet den Basisfall für diese Anforderung.
  • S \rightarrow \ ist da, um das $ zwischen der linken und der rechten Seite zu setzen.
  • Bei rekursivem Benutzen von werden links immer doppelt so viele a’s hinzugefügt wie rechts.
  • Nach Rekursionen ist das Wort gebildet und kann mithilfe von S \rightarrow \ getrennt werden.

Dadurch erkennt diese Grammatik die Sprache .

b) Geben Sie einen Kellerautomaten an, der akzeptiert (mit leerem Keller oder mit Endzuständen). Erklären Sie kurz, warum Ihr Automat genau akzeptiert.

Ein Kellerautomat , der die Sprache L = \{a^{2n}\a^n \mid n \in \mathbb{N}_{\gt0}}$ akzeptiert, wird wie folgt definiert:

Definition des Kellerautomaten:

  • Zustände:
  • Eingabealphabet: \Sigma = \{a, \}$
  • Kelleralphabet:
  • Startzustand:
  • Startkellersymbol:
  • Akzeptierende Zustände:

Übergangsfunktion :

  1. Initiale Phase (Doppelte a’s auf den Keller legen):

  2. Dollarzeichen erkennen:

    • \delta(q_0, \, a) = {(q_1, a)}$
  3. a’s nach dem Dollarzeichen verarbeiten:

  4. Keller entleeren und akzeptieren:

Erklärung:

  1. Phase 1 (Initiale Phase):

    • Der Automat liest die a’s und legt sie auf den Keller, sodass die Anzahl der a’s im Keller doppelt so groß ist wie die Anzahl der a’s, die nach dem Dollarzeichen gelesen werden müssen.
  2. Phase 2 (Dollarzeichen erkennen):

    • Sobald das Dollarzeichen \$$ gelesen wird, wechselt der Automat in den Zustand q_1$.
  3. Phase 3 (Nachfolgende a’s verarbeiten):

    • Der Automat liest die a’s nach dem Dollarzeichen und entfernt ein a vom Keller für jedes gelesene a.
  4. Phase 4 (Akzeptieren):

    • Wenn der Keller leer ist und das Startkellersymbol erreicht wird, wechselt der Automat in den akzeptierenden Zustand und akzeptiert die Eingabe.

FSK6-2 CYK-Algorithmus (2 Punkte)

Aufgabenstellung

Sei die Grammatik ({A_1, A_2, A_3, A_4, A_5}, \{\, #}, P, A_1)$ mit

a) Prüfen Sie mit dem CYK-Algorithmus, ob die folgenden Wörter und in sind. Erstellen Sie dazu für jedes Wort die entsprechende Tabelle des Algorithmus und erklären Sie anhand der Tabelle, ob das Wort in ist.

i) w_1 = \#$##$

CYK-Algorithmus zur Überprüfung von w_1 = \#$##$

Gegebene Grammatik :

Eingabewort: w_1 = \#$##$

Schritt 1: Initialisierung der Tabelle

Schritt 2: Rekursion

12345
1
2-
3--
4---
5----

Fazit:

  • Das Wort w_1 = \#$##L(G)A_{1} \notin V_{1,5}$

Falsche Lösung zum Verständnis worauf zu achten ist

  • Fehler tritt schon in Zeile 2 auf, wo nur als Option betrachtet wird, wobei auch legitim wäre
  • ist nicht korrekt da man immer das Kreuzprodukt aus den ausgewählten Zeilen bilden muss z.B () und oder beide nicht dargestellt werden können
12345
1
2-
3--
4---
5----

Zeile 2:

  • , da und bilden kann
  • , da und bilden kann
  • , da und bilden kann
  • , da und bilden kann

Zeile 3:

  • , da () und () bilden kann
  • , da () und () bilden kann
  • , da () und () bilden kann

Zeile 4:

    • bilden was nicht abgebildet werden kann
    • bilden was nicht abgebildet werden kann
    • bilden was nicht abgebildet werden kann
    • bilden was nicht abgebildet werden kann
    • bilden was nicht abgebildet werden kann
    • bilden was nicht abgebildet werden kann

Zeile 5:

    • bilden und was nicht abgebildet werden kann
    • bilden und was nicht abgebildet werden kann
    • bilden und was nicht abgebildet werden kann
    • bilden und was nicht abgebildet werden kann

ii) w_2 = \$$##$

Gegebene Grammatik :

Eingabewort: w_2 = \$$##$

Schritt 1: Initialisierung der Tabelle

Schritt 2: Rekursion

12345
1
2-
3--
4---
5----

Zeile 2:

  • =
  • =
  • =
  • =

Zeile 3:

Zeile 4:

Zeile 5:

Fazit:

  • Das Wort w_1 = \#$##L(G)A_{1} \in V_{1,5}$

b) Geben Sie alle weiteren Wörter an, für die sich aus den Tabellen ergibt, dass ist.

Unsicher wie zu lösen ist

Identifikation weiterer Wörter in

Die Tabellen zeigen, dass die Grammatik die folgenden Kombinationen von $ und # zulässt:

  1. Länge 2:

    • $ #
  2. Länge 3:

    • $ # #
  3. Länge 4 und mehr:

    • $ # $ #
    • $ $ # #
    • # $ $ #

Schlussfolgerung

Die Grammatik erlaubt Kombinationen von $ und #, die den Ableitungsregeln entsprechen. Insbesondere alle Wörter, die durch Kombinationen und Anwendungen der Produktionen von , , , und entstehen, sind Teil der Sprache .

FSK6-3 Begrenzter Keller

a) Ein Kellerautomat mit -begrenzt​em Keller ist ein Kellerautomat, bei dem maximal Symbole auf dem Keller liegen können. Wenn der Keller voll ist, können Übergänge, die ein Symbol auf den Keller legen würden, nicht gewählt werden.

Zeigen Sie, dass für jeden Kellerautomaten und gilt:

Hierbei nehmen wir an, dass mit leerem Keller akzeptiert.

Beweis:

  1. Definition der akzeptierten Sprache:

    • Ein Kellerautomat akzeptiert ein Wort , wenn durch Zustandsübergänge der Startzustand in einen akzeptierenden Zustand überführt wird und der Keller nach Verarbeitung von leer ist.
  2. Eigenschaften des -begrenzten Kellers:

    • Ein Kellerautomat mit -begrenztem Keller kann höchstens Symbole im Keller haben. Bei vollem Keller sind Übergänge, die Symbole hinzufügen, nicht möglich.
  3. Behauptung:

    • Jedes Wort, das vom -begrenzten Kellerautomaten akzeptiert wird, wird auch vom ursprünglichen Kellerautomaten ohne Begrenzung akzeptiert:
  4. Simulation von mit -begrenztem Keller:

    • Ein Wort wird vom -begrenztem Kellerautomaten akzeptiert, wenn es eine Zustandsübergangsfolge gibt, die vollständig verarbeitet und den Keller leer macht, ohne jemals mehr als Symbole im Keller zu haben.
    • Diese Zustandsübergänge können auch im ursprünglichen Kellerautomaten (ohne Begrenzung) ausgeführt werden, da keine Begrenzung der Symbolanzahl im Keller hat.
  5. Formalität des Beweises:

    • Angenommen, . Das bedeutet, dass es eine akzeptierende Berechnung des -begrenzten Kellerautomaten für gibt, die den Keller nie mehr als Symbole enthalten lässt.
    • Da diese Berechnung auch im unbegrenzten Kellerautomaten möglich ist, akzeptiert ebenfalls .
  6. Schlussfolgerung:

    • Jede akzeptierende Berechnung des -begrenzten Kellerautomaten ist auch eine akzeptierende Berechnung des unbegrenzten Kellerautomaten. Daher gilt:

b) Zeigen Sie, dass für alle die Kellerautomaten mit -begrenztem Keller genau die regulären Sprachen beschreiben.

Lösung (direkte Beweiskombination)

1. Kellerautomaten mit -begrenztem Keller akzeptieren reguläre Sprachen:

  • Jede reguläre Sprache kann durch einen deterministischen endlichen Automaten (DFA) akzeptiert werden.
  • Ein Kellerautomat mit -begrenztem Keller kann dieselbe Sprache akzeptieren, indem er den Keller nicht nutzt oder nur eine konstante Anzahl von Symbolen speichert (maximal ).

2. Kellerautomaten mit -begrenztem Keller akzeptieren nur reguläre Sprachen:

  • Der Keller ist auf Symbole begrenzt, daher gibt es nur endlich viele mögliche Kellerinhalte.
  • Kombiniere die Zustände des Kellerautomaten und die möglichen Kellerinhalte, um eine endliche Zustandsmenge zu erhalten.
  • Dadurch kann ein DFA konstruiert werden, der dieselbe Sprache akzeptiert wie der Kellerautomat mit -begrenztem Keller.

Schlussfolgerung:

Kellerautomaten mit -begrenztem Keller beschreiben genau die regulären Sprachen, da sie einerseits reguläre Sprachen akzeptieren können und andererseits nur reguläre Sprachen akzeptieren.


FSK6-4 Homomorphismen

Aufgabenstellung:

Gegeben Alphabete und bezeichnen wir eine Abbildung als (Monoid-)Homomorphismus, wenn sie strukturerhaltend ist, d.h. wenn gilt:

Für sei .

Man kann leicht zeigen, dass für alle Sprachen und Homomorphismen gilt:

a) Beweisen Sie für alle Sprachen und Homomorphismen :

Beweis für

Gegeben:

  • Zwei Sprachen
  • Ein Homomorphismus

Behauptung:

Beweis:

  1. Definition der Konkatens von Sprachen:

  2. Bild der Konkatens zweier Sprachen unter :

    Da , gibt es und mit . Somit:

  3. Eigenschaft des Homomorphismus:

    Also:

  4. Ersetzung in der Menge:

    Dies ist per Definition:

  5. Folgerung:

Beweis für

Gegeben:

  • Eine Sprache
  • Ein Homomorphismus

Behauptung:

Beweis:

  1. Definition des Kleene-Sterns:

    wobei und .

  2. Bild unter :

  3. Eigenschaft des Homomorphismus für Konkatens:

    Beweis durch Induktion über (k):

    • Induktionsanfang:

    • Induktionsannahme: Angenommen, es gilt .

    • Induktionsschritt:

Daher gilt für alle .

  1. Zusammensetzung der Kleene-Sterns:

  2. Folgerung:

Damit sind beide Aussagen bewiesen:

b) Beweisen Sie für alle regulären Sprachen und Homomorphismen : Wenn regulär ist, dann ist auch regulär.

Beweis:

  1. Gegeben: ist eine reguläre Sprache über dem Alphabet .

  2. Eigenschaft regulärer Sprachen: Da regulär ist, existiert ein deterministischer endlicher Automat (DFA) , der erkennt.

  3. Homomorphismus : Der Homomorphismus ist eine Abbildung, die strukturerhaltend ist:

  4. Transformation des Automaten: Wir konstruieren einen neuen Automaten , der erkennt. Dabei wird die Übergangsfunktion so angepasst, dass sie auf die Bilder der Symbole unter angewendet wird.

  5. Konstruktion von :

    • Der neue Automat hat denselben Zustandsraum , Startzustand , und Endzustände wie .
    • Die Übergangsfunktion wird so definiert, dass sie den Übergängen von folgt, aber für die Symbole in , die durch abgebildet werden.
  6. Erkennung von : Da durch die Anwendung von auf die Übergangsfunktion von konstruiert wird, erkennt die Sprache .

Schlussfolgerung:

Da ein DFA ist und DFA’s genau die regulären Sprachen erkennen, ist ebenfalls regulär.

Zusammenfassung:

Wenn regulär ist, gibt es einen DFA, der erkennt. Durch Transformation dieses DFA unter dem Homomorphismus erhält man einen neuen DFA, der erkennt. Daher ist regulär.

c) Zeigen Sie, dass über dem Alphabet die Sprache

nicht regulär ist. Geben Sie zu diesem Zweck einen Homomorphismus an, so dass ist. Da bekanntlich nicht regulär ist, kann dann auch nicht regulär sein.

Um zu zeigen, dass die Sprache nicht regulär ist, verwenden wir einen Homomorphismus , der auf eine bekannte nicht-reguläre Sprache abbildet.

Schritt-für-Schritt Beweis:

  1. Definition der Sprache :

  2. Homomorphismus : Wir definieren mit dem Alphabet wie folgt:

  3. Bild der Sprache unter :

    Da und , vereinfacht sich das zu:

    Also:

  4. Nicht-Regulärität von : Es ist bekannt, dass die Sprache nicht regulär ist.

  5. Schlussfolgerung: Da nicht regulär ist und ein Homomorphismus ist, muss auch die ursprüngliche Sprache nicht regulär sein.

Fazit:

Durch die Abbildung der Sprache auf die bekannte nicht-reguläre Sprache mittels des Homomorphismus , haben wir gezeigt, dass nicht regulär ist.