0 Daumen
411 Aufrufe

Hallo,

ich versuche die Lösung zu folgender Frage zu verstehen:

Frage:
Eine Sprache \(L \subseteq A*\) sei wie folgt induktiv definiert:
- \(\varepsilon \in L\)
- wenn \(x \in L\) ist, dann ist \(aax \in L\)
- wenn \(y, z \in L\) sind, dann ist \(y \mathrm{b} z \in L\)
\(L\) enthalte sonst keine Wörter aus \(A*\).
Geben Sie alle Wörter \(w \in L\) an, für die \(|w| \leq 3\) ist.

Lösung:
\(\varepsilon, b, a a, b b, a a b\), baa, bbb

Ich verstehe nicht, wieso nicht auch a ∈ L gilt. Denn immerhin hat a eine Länge < 3, außerdem heißt es doch: wenn \(x \in L\) ist, dann ist \(aax \in L\). Daraus schlussfolgere ich, dass damit z.B. baa in L sein kann, erstmal überhaupt a in L sein muss.

Wo liegt mein Denkfehler? Dankeschön.

Avatar von

1 Antwort

0 Daumen
 
Beste Antwort

Die zweite Regel erlaubt es, aus einem Wort aus L durch Voranstellen von "aa" (also zwei(!) a's) ein neues Wort aus L zu erzeugen. Da dies die einzige Möglichkeit ist, a's einzubauen, muss die Anzahl der a's in einem Wort aus L immer gerade sein.

Avatar von

Danke für deine Antwort, jetzt verstehe ich es.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community