Beweisen Sie durch vollständige Induktion die folgende Aussage.... (ab)^{i}(cd)^{i} Element L

Question

Es sei A = {a, b, c, d}. Eine Folge formaler Sprachen L_{n} sei wie folgt definiert:

$$\begin{aligned} L _ { 0 } & = \{ \epsilon \} \\ \forall n \in \mathbb { N } _ { 0 } : L _ { n + 1 } & = \{ a b \} \cdot L _ { n } \cdot \{ c d \} \end{aligned}$$

Außerdem sei \( L = \bigcup _ { i = 0 } ^ { \infty } L _ { i } \).

Beweisen Sie durch vollständige Induktion die folgende Aussage:

$$\forall i \in \mathbb { N } _ { 0 } : ( a b ) ^ { i } ( c d ) ^ { i } \in L$$

Answer 1

Stelle erst mal mit der Rekursionsformel ein Paar solche L_(k) auf

L_(0) = €

L_(1) = (ab) € (cd) = abcd

L_(2) = (ab) abcd (cd) = ababcdcd = (ab)^2(cd)^2

Allgemein

L_(i) = (ab)^{i}(cd)^{i} , i Element N.

Verankerung und Induktionsbehauptung hast du nun.

Nun der Induktionsschritt. Ind. beh. L_(i+1) = (ab)^{i+1}(cd)^{i+1}

Ind. bew.

L_(i+1) = (ab) ((ab)^{i}(cd)^{i}) (cd)  | Assoziativgesetz

= ( (ab) (ab)^{i})((cd)^{i} (cd) )

= (ab)^{i+1} (cd)^{i+1}  q.e.d. Induktionsschritt.

(ohne Gewähr) Rechnungen genau mit eurem Skript abgleichen.