Question

Sprache L(G) angeben die von Grammatik erzeugt wird.

Es sei G (N, T, S, P) die Grammatik mit den Nichtterminalsymbolen N = {S, E, T, Z, Q, C, D}, den Terminalsymbolen T = {0, 1} und den Produktionen

$$ P = \\ \{ s \rightarrow E | z | Q, \\ \mathrm { E } \rightarrow 1 \mathrm { E } | 0 \mathrm { T } | \mathbf { \epsilon }, \\ \mathbf { T } \rightarrow 1 \mathrm { T } | \mathrm { OE }, \\ Z \rightarrow 1 Z | O E | \epsilon, \\ \mathrm { Q } \rightarrow \mathrm { CD }, \\ \mathrm { C } \rightarrow \mathrm { 0C } | 0, \\ D \rightarrow 1 D | 1 \} $$

a) Leiten Sie aus dem Startsymbol das Wort 11010111010 ab. Geben Sie dabei jeden Ableitungsschritt an.
b) Leiten Sie aus dem Startsymbol das Wort 11000110110 ab. Geben Sie dabei jeden Ableitungsschritt an.
der sich von dem Ableitungsbaum aus Teilaufgabe c) unterscheidet.
c) Zeichnen Sie einen Ableitungsbaum für das Wort 0000001111111.
d) Zeichnen Sie einen zweiten Ableitungsbaum für das Wort 0000001111111, der sich von dem Ableitungsbaum aus Teilaufgabe c) unterscheidet.
e) Geben Sie die Sprache L(G) an, die die Grammatik erzeugt.

Die Aufgaben a) bis d) waren kein Problem. Jetzt hänge ich allerdings an der e) fest und komme nicht weiter.

Mein Ansatz war L(G) = {0ⁱ1^j  |  i,j ∈ ℕ₀} aber das kann ja so nicht stimmen. Ich wäre um jegliche Hilfe sehr dankbar.

Answer 1

Ich würde sie getrennt betrachten für E,Z und Q und die Vereinigung bilden, E und Z könnte man dann noch zusammenfassen.

$$\begin{aligned}L(G)&= \left\{1^*,01^*0\right\}^*   \quad\cup\quad   \{1^*0\}\circ\left\{1^*,01^*0\right\}^*   \quad\cup\quad  \{0^*1^*\}\\&= \{1^*0,\epsilon\}\circ\left\{1^*,01^*0\right\}^*   \quad\cup\quad  \{0^*1^*\}\end{aligned}$$

Comments

Mir ist gar nicht in den Sinn gekommen das ganze getrennt zu betrachten... hätte ich also noch lange rumprobieren können. Jetzt ist aber alles klar.

Und nochmal vielen Dank für die Hilfe.