Sei Σ = {a, b} ein gegebenes Alphabet. Die formalen Sprachen L1 ⊆ Σ∗ und L2 ⊆ Σ∗ sind wie folgt rekursiv definiert:
L1 = {ε} ∪ a ◦ L1 ◦ b ∪ b ◦ L1 ◦ a ∪ L1 ◦ L1
L2 = {a} ∪ a ◦ L2 ◦ b ∪ a ◦ L2
a) Geben Sie eine einfache verbale Beschreibung für die Sprachen L1 und L2.
Entscheiden Sie, zu welcher(n) Sprache(n) die folgenden Wörter gehören:
w = aabab - w´ = abbaaabb - w´´ = aaaabb
Begründen Sie positive Antworten durch Angeben eines Schemas mit dem das Wort als Element der Sprache Li nach den gegebenen Regeln aufgebaut werden kann.
b) Wieviele Wörter der Länge 4 gehören zur Sprache L1 und wieviele Wörter der Länge 8 gehören zur Sprache L2? Begründen Sie die Antworten kurz!
