0 Daumen
206 Aufrufe

Thema: Theo1-Kellerautomat, Chomsky Hierachie

Aufgabe 1:

Sei L = {xnb3n | n ∈ N}.

a) Zeichnen Sie den Graph eines DPDA M mit L(M ) = L auf.

b) Geben Sie die formale Beschreibung von M an


Aufgabe 2:

Sei G = (V, Σ, P, S) mit V = {S, W, X, Y, Z}, Σ = {a, b, c} und
P = { S → XbZc|bcY a,
W → W c|Y ZX|Z,
X → Y a|Y,
Y → c|aY |bZ,
Z → ZZ|W }

gegeben.

Leiten Sie eine Grammatik G′ in Chomsky-Normalform mit L(G) = L(G′) her. Geben Sie alle hierfür notwendigen Zwischenschritte an.

Avatar von

1 Antwort

0 Daumen

Antwort mit KI erzeugt

Aufgabe 1:

Teil a: Zeichnen Sie den Graph eines DPDA M mit \(L(M) = L\)

Sei \(L = \{ x^n b^3n \mid n \in \mathbb{N} \}\).

Ein deterministischer Kellerautomat (DPDA) für diese Sprache hat folgende Aufgaben:
1. Er muss sicherstellen, dass die Anzahl der x korrekt gezählt wird.
2. Er muss danach sicherstellen, dass die Anzahl der b dreimal so groß ist wie die Anzahl der x.

Ein DPDA kann wie folgt konstruiert werden:

- Zustände: \( q_0 \) (Startzustand), \( q_1 \) (zum Lesen von b's), \( q_2 \) (zum Lesen der restlichen b's)
- Eingabealphabet: \( \{x, b\} \)
- Kelleralphabet: \( \{Z, X\} \) (Z ist das Kelleranfangssymbol)
- Anfangszustand: \( q_0 \)
- Anfangskellersymbol: \( Z \)
- Endzustände: \( q_0, q_1 \)

Der Übergangsfunktionen lässt sich wie folgt beschreiben:

1. \((q_0, x, Z) \rightarrow (q_0, XS)\) - bei Lesen von x wird X auf den Keller gelegt.
2. \((q_0, x, X) \rightarrow (q_0, XX)\) - bei Lesen von x wird X auf den Keller gelegt.
3. \((q_0, b, X) \rightarrow (q_1, \epsilon)\) - Wechsel in Zustand \(q_1\) beim Lesen des ersten b (drei X sind erforderlich).
4. \((q_1, b, X) \rightarrow (q_1, X)\) - behält den Zustand bei, wenn b und X im Keller gelesen werden (drei bs für jede X).
5. \((q_0, \epsilon, S) \rightarrow (q_0, S)\) - akzeptiert nur, wenn der Keller leer ist.

Graph der DPDA \(M\):

         +-------+ X      |       V(q0, x)|->-(q0, XZ)         +       |          |       +         V       |  XS     |       |(q0, x)|->-(q0, XX)->(q1, epsilon)        +       |        |       +--------------------------+        V                                b | q0    (b, X) q1  +                       (b, X)| S <-  |-> |(q1, X)-> (q0, S)        +                   +                        



Aufgabe 1.b: Formale Beschreibung von \( M \):

Der DPDA \( M \) ist formal wie folgt beschrieben:

\( M = (Q, \Sigma, \Gamma, \delta, q_0, Z, F) \)

Wobei:
- \( Q = \{ q_0, q_1 \} \) die Zustandsmenge,
- \( \Sigma = \{ x, b \} \) das Eingabealphabet,
- \( \Gamma = \{ X, Z \} \) das Kelleralphabet,
- \( \delta \) die Übergangsfunktion,
- \( q_0 \) der Anfangszustand,
- \( Z \) das Anfangskellersymbol,
- \( F = \{ q_1 \} \) die Menge der Endzustände.

Die Übergangsfunktion \(\delta\) ist definiert als:
- \( \delta(q_0, x, Z) = (q_0, XZ) \)
- \( \delta(q_0, x, X) = (q_0, XX) \)
- \( \delta(q_0, b, X) = (q_1, \epsilon) \)
- \( \delta(q_1, b, X) = (q_1, X) \)
- \( \delta(q_0, \epsilon, S) = (q_0, S) \)


Aufgabe 2:

Grammatik G in Chomsky-Normalform umwandeln

Gegeben:

\( G = (V, \Sigma, P, S) \) mit:
- \( V = \{ S, W, X, Y, Z \} \)
- \(\Sigma = \{ a, b, c \} \)
- \( P \) die Produktionsregeln:
- 1: \( S \rightarrow XbZc \mid bcY a \)
- 2: \( W \rightarrow Wc \mid YZX \mid Z \)
- 3: \( X \rightarrow Ya \mid Y \)
- 4: \( Y \rightarrow c \mid aY \mid bZ \)
- 5: \( Z \rightarrow ZZ \mid W \)

Für die Umformung in Chomsky-Normalform (CNF) folgen wir diesen Schritten:

1. Schritt 1: Entfernen von \(\epsilon\)-Produktionen, falls vorhanden (es gibt keine)
2. Schritt 2: Entfernen von Unit-Produktionen \(A \rightarrow B\), wobei A, B \in V (Variablen)
Hier haben wir \( X \rightarrow Y \), was eine Einheitproduktion ist. Ersetzen wir dies.
- \( X \rightarrow c \mid aY \mid bZ \) (von \( Y \rightarrow c \mid aY \mid bZ \))

Also, Regel 3 wird: \( X \rightarrow Ya \mid c \mid aY \mid bZ \)

3. Schritt 3: Beseitigen der überschüssigen Produktionen
Regel 1: \( S \rightarrow XbZc \mid bcY a \)

Zerlegen der rechten Seite, sodass alles \( XY \)-Produktionen werden:
\( S \rightarrow XC \mid AB \) wenn \( XbZc \rightarrow X\alpha B \mid AbZc, \)
also Regeln hinzufügen:
- \( X \rightarrow xc \)
- \( Zc => YC \)

4. Schritt 4: Bringen jeder Produktion genau 2 Variablen
\( S \Rightarrow ST\mid AB\) (konvertieren Sie)
Addieren:
- \( A \rightarrow bY \mid aZ \)
- \( xy->XX \)

Die Endform der Grammatik in CNF ist also:

- \( G' = ( \{ S, Z, Y, W, X, \sigma^{1}, \pi^{1} \ldots \}, \Sigma, \gamma \subset \sigma ) \)

Avatar von 4,6 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community