+1 Daumen
1,7k Aufrufe

Aufgabe - Korrekte Klammerungen:

Gegeben sei das Alphabet \( \Sigma=\{() \),\( \} bestehend aus einer öffnenden Klammer und einer \) schließenden Klammer.

Wir definieren zwei Sprachen \( L, K \subseteq \Sigma^{*} \). Die Sprache \( L \) ist definiert als diejenige Sprache, die die folgenden Regeln erfüllt:

- Das leere Wort \( \varepsilon \) ist in \( L \) enthalten.
- Sind \( u, v \) in \( L \), so ist auch \( u v \in L \).
- Ist \( u \in L \), dann ist auch \( (u) \in L \).
- Ein Wort ist nur in \( L \), wenn es aufgrund der obigen Regeln in \( L \) ist.

Die Sprache \( K \) ist gegeben durch
\( \left.K=\left\{\left.w \in \Sigma^{*}|| w\right|_{(}=|w|\right) \text { und für alle } u, v \text { mit } u v=w \text { gilt }|u|_{(} \geq|u|_{)}\right\} . \)

Dabei bezeichnet \( |w|_{a} \) die Anzahl der Vorkommen des Buchstabens \( a \) im Wort \( w \).

a) Zeigen Sie \( L=K \).

b) Finden Sie eine Typ-2 Grammatik für \( L \) bzw. \( K \).

Avatar von

Das könnte etwas mit konkatenieren | (zusammensetzen) zu tun haben. Warum das genau tiefgestellt ist, weiss ich nicht. Hast du in deinen Unterlagen keine Einführung der Bezeichnungen?

Ohne deine Unterlagen muss man einfach raten.

Wenn ich L lese, vermute ich, dass in der Sprache neben dem leeren Wort € nur vollständig geklammerte Klammern vorkommen.

Also €,

() wegen 3),

()()  wegen 2),

 (()) wegen 3)

usw. Z.B. auch ((()()))()

usw.

Nun muss gemäss Fragestellung K dasselbe geben. Da kannst du vielleicht auch von hinten her die Abkürzungen zu verstehen versuchen.

Korrekt geklammerte arithmetische Ausdrücke
Wir definieren eine Grammatik
\( G=(\{E, T, F\},\{(,), a,+, *\}, P, E) \)

Hierbei steht \( E \) für Expression (Ausdruck), \( T \) für Term, sowie \( F \) für Faktor. Die Regelmenge \( P \) sei die folgende:
\( \begin{array}{l} P=\{E \rightarrow T, \quad E \rightarrow E+T, \quad T \rightarrow F, \\ T \rightarrow T * F, \quad F \rightarrow a, \quad F \rightarrow(E)\} \\ \end{array} \)
wobei \( u \rightarrow v \) generell als andere Schreibweise für \( (u, v) \) anzusehen ist.
Wir geben Ableitungen von Satzformen in dieser Grammatik an:
\( \begin{array}{l} E \Rightarrow_{G} T \Rightarrow_{G} F \Rightarrow_{G} a \\ E \Rightarrow_{G} T \Rightarrow_{G} T * F \Rightarrow_{G} F * F \Rightarrow_{G} a * F \Rightarrow_{G} a *(E) \end{array} \)

Es gilt \( a \in L(G) \) (warum?), aber \( a *(E) \notin L(G) \) (warum nicht?). Können wir \( a *(a+a) \in L(G) \) zeigen?

Weiß net, ob dir das weiterhilft, weil mir bringt das auch net

\( \left| w \right|_{(} \) könnte die Anzahl der öffnenden (linken) Klammern im Wort \(w\) bezeichnen.

az0815. Ach ja. Das steht ja direkt in der Linie darunter.

Nun wissen wir, dass ein Wort w gleich viele öffnende wie schliessenden Klammern enthält und kein Wortanfang mehr schliessende als öffnende Klammern enthalten kann. Das gibt dann wieder die vermuteten korrekten Klammerungen von L.

Es steht doch da, dass \( |w|_a \) die Anzahl des Vorkommens des Buchstabens \( a \) im Wort \( w \) ist.

Und das bedeutet was im Zshs mit Klammern?

Dein Alphabet besteht nur aus den beiden Klammern ( und ) .

|w|(  = |w|)

Lies: Das Wort w enthält gleich viele öffnende wie schliessende Klammern.

und

uv = w . Das Wort w besteht aus u und v .

und u enthält nicht weniger öffnende wie schliessende Klammern.

Die zweite Bedingung für ein Wort \(w\) aus der Sprache \(K\) besagt anschaulich, dass beim zeichenweisen Aufschreiben des Wortes \(w\) von links nach rechts immer mindestens so viele öffnende (linke) Klammern wie schließende (rechte) Klammern auf dem Papier stehen, also niemals mehr schließende als öffnende.

1 Antwort

0 Daumen

Antwort mit KI erzeugt

a) Zeigen Sie \( L=K \).

Um zu zeigen, dass \( L=K \), müssen wir beweisen, dass alle Wörter in \( L \) auch in \( K \) sind und umgekehrt, dass alle Wörter in \( K \) auch in \( L \) sind.

Beweis \( L \subseteq K \):

1. Basis der Induktion (Induktionsanfang): Das leere Wort \( \varepsilon \) ist in \( L \) und erfüllt auch die Bedingungen von \( K \), da \( |\varepsilon|_{(}=0=|\varepsilon|_{)} \) und für alle Zerlegungen \( u, v \), mit \( u v = \varepsilon \), gilt trivial, dass \( |u|_{(} \geq |u|_{)} \) (da sowohl \( u \) als auch \( v \) auch das leere Wort sein müssen).

2. Induktionsschritt:

- Regel 2 (Konkatenation): Angenommen, \( u, v \in L \). Nach Induktionsannahme gehören \( u, v \) auch zu \( K \), was bedeutet, dass für alle Zerlegungen von \( u \) und \( v \) die Zahl der öffnenden Klammern größer oder gleich der schließenden Klammern ist und insgesamt die Anzahl der öffnenden und schließenden Klammern jeweils gleich ist. Die Konkatenation \( uv \) erhält diese Eigenschaft, da die Reihenfolge und die Anzahl der Klammern beibehalten werden. Also ist \( uv \in K \).

- Regel 3 (Hinzufügen von Klammern): Für ein Wort \( u \in L \) (und nach Annahme in \( K \)), erzeugt das Hinzufügen von Klammern um \( u \) ein Wort \( (u) \), welches die Anzahl der öffnenden und schließenden Klammern erhält und sicherstellt, dass jede Zerlegung \( u' \) von \( (u) \), die vom Anfang bis zu einem beliebigen Punkt im Wort reicht, mehr oder gleich viele öffnende Klammern als schließende Klammern hat. Dies entspricht direkt der Definition von \( K \), so dass \( (u) \in K \).

Damit haben wir gezeigt, dass wenn ein Wort in \( L \) ist, es auch die Bedingungen von \( K \) erfüllt, was \( L \subseteq K \) beweist.

Beweis \( K \subseteq L \):

Um \( K \subseteq L \) zu zeigen, berücksichtigen wir, dass jedes Wort \( w \in K \) nach Definition eine gleiche Anzahl von öffnenden und schließenden Klammern hat und für alle Zerlegungen \( u, v \) mit \( u v = w \) gilt, dass \( |u|_{(} \geq |u|_{)} \). Diese zwei Bedingungen garantieren, dass das Wort \( w \) korrekt geklammert ist, da von Anfang an bei jeder Teilzeichenkette die Anzahl der öffnenden Klammern immer größer oder gleich der Anzahl der schließenden Klammern ist und insgesamt gleich ist.

1. Das leere Wort \( \varepsilon \) ist trivialerweise in \( L \).

2. Für jedes nicht-leere Wort in \( K \) können wir durch Induktion ausgehend von einfacheren, kürzeren Wörtern, die bereits nach den Regeln von \( L \) gebildet wurden, zeigen, dass wir dieses durch Anwenden der Regeln 2 und 3 erhalten können. Da jedes Wort \( w \in K \) durch ein Set von Regeln konstruiert werden kann, das sicherstellt, dass es korrekt geklammert ist, und \( L \) genau solche Wörter umfasst, folgt, dass jedes Wort in \( K \) auch durch die Regeln von \( L \) konstruiert werden kann.

Somit haben wir gezeigt, dass ein Wort, wenn es in \( K \) ist, auch in \( L \) ist, was \( K \subseteq L \) beweist.

Da wir sowohl \( L \subseteq K \) als auch \( K \subseteq L \) bewiesen haben, folgt \( L = K \).

b) Finden Sie eine Typ-2 Grammatik für \( L \) bzw. \( K \).

Da \( L = K \), genügt es, eine Typ-2-Grammatik (kontextfreie Grammatik) für \( L \) zu finden, und diese wird auch für \( K \) gelten.

Grammatik G für \( L \):

- \( G = (V, \Sigma, R, S) \)
- Nicht-terminale Symbole: \( V = \{S\} \)
- Terminale Symbole: \( \Sigma = \{'(', ')'\} \)
- Startsymbol: \( S \)
- Regeln \( R \):
1. \( S \rightarrow SS \) (Konkatenation zweier Wörter in \( L \))
2. \( S \rightarrow (S) \) (Hinzufügen von Klammern um ein Wort in \( L \))
3. \( S \rightarrow \varepsilon \) (Das leere Wort ist in \( L \))

Diese Grammatik erzeugt alle korrekt geklammerten Ausdrücke, die möglich sind, indem sie die Basisregeln für \( L \) (und somit \( K \)) nachahmt: Das leere Wort ist enthalten, beliebige Konkatenationen korrekt geklammerter Wörter sind möglich, und das Umklammern eines solchen Wortes ist ebenfalls möglich.
Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community