0 Daumen
548 Aufrufe

Aufgabe:

Erstellen Sie kontextfreie Grammatiken für die folgenden Sprachen. Das Alphabet ist jeweils Σ = {0, 1}
a) L = {w ∈ {0, 1}∗ | w enthält das Teilwort 0 und die Länge von w ist ungerade}
b) L = {w ∈ {0, 1}∗ | w enthält das Teilwort 11 und die Länge von w ist gerade}
c)  L = { w | die Länge von w ist ungerade und das Symbol in der Mitte ist eine 1 }


Problem/Ansatz:

Könnten meine Lösungen auch stimmen?
a)
blob.png

Text erkannt:

\( \begin{array}{rl}G: & (\mathbb{\Sigma}, P, S) \quad \Sigma=\{0,1\} \quad N=\{S, A, B\} \\ & S \longrightarrow A A O|O A A| A O A \mid O \\ & \longrightarrow B O|B 1| 0 \mid 1 \\ B & O O|O 1| 10 \mid 11\end{array} \)


b)
blob.png

Text erkannt:

\( \mathcal{C}:=(N, \Sigma, P, S) \quad \Sigma=\{0,1\} \quad \mathbb{R} N=\{\}, A, B\} \)
\( S \rightarrow 11|11 \mathrm{AA} \eta \mathrm{AA} 11| \mathrm{A} 11 \mathrm{~A} \)
\( A \rightarrow O B|\wedge B| 011 \)
\( B \rightarrow O 0|O 1| 10 \mid 11(0 B \mid 1 B \)


c)
blob.png

Text erkannt:

\( \begin{aligned} & G=(N, \Sigma, P, S) \\ S \rightarrow &1) A 1 A \\ A \rightarrow &O O A|O 1 A| 10 A|11 A| 00 \mid 01111) 10 \end{aligned} \)

Avatar von

1 Antwort

0 Daumen

a) Das Wort \(111101111\) kann nicht abgeleitet werden obwohl \(111101111\in L\) ist. Grund dafür ist, dass nur Wörter bis zu einer Länge von 7 abgeleitet werden können.

Deine Vorschläge für b) und c) leiden unter ähnlichen Problemen.

Avatar von 5,7 k

Danke vielmals Oswald. Hätten Sie mir einen Trick, wie ich solche Regel bestimmen könnte oder wie man hier vorgeht?

Ich bin ein bisschen verloren, bei solchen Aufgaben.

Meine Strategie ist R̶u̶m̶ ̶p̶r̶o̶b̶i̶e̶r̶e̶n̶ rumprobieren.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community