Zeigen Sie: A* = {0n | n ∈ ℕ0} ∪ {0n11m | n, m ∈ ℕ0} ∪ {0n11m00p, 0n11m01p | n, m, p ∈ ℕ0}

Question

Aufgabe:

Zeigen Sie:

Sei A* = {0, 1}*, also eine beliebige Folgen an Symbolen dieser Menge.

A* = {0ⁿ | n ∈ ℕ₀} ∪ {0ⁿ11^m | n, m ∈ ℕ₀} ∪ {0ⁿ11^m0d | d ∈ A* und n, m ∈ ℕ₀}

Problem/Ansatz:

Die Richtung von rechts nach links ist klar, das folgt direkt aus der Definition.

Aber wie genau zeigt man die andere Richtung. Man nimmt sich ein beliebiges x aus A*. Muss man jetzt einfach das Wort durchgehen, also wenn man zunächst eine 0 hat, dann muss man schauen, ob noch eine 1 kommt etc. oder kann man das anders machen?

Comments

Um Mengengleichheit von zwei Mengen \(A\) und \(B\) zu beweisen, musst du zeigen, dass \(A\subset B\) und \(B \subset A\) ist.

Answer 1

Sei \(x\in A^*\).

Fall 1. \(x\) enthält keine \(1\). Dann ist \(x \in \{0^n | n \in \mathbb{N}_0\}\).

Fall 2. \(x\) enthält eine \(1\) und nach der ersten \(1\) kommt nie wieder eine \(0\). Dann ...

Fall 3. \(x\) fällt weder unter Fall 1, noch unter Fall 2. Dann ...