Beweisen Sie, dass gilt: L1 · (L2 · L3) ⊆ (L1 · L2) · L3.

Question

Es sei A ein Alphabet, und für jede formale Sprache L ⊆ A* und jede formale Sprache S ⊆ A* sei

L · S = {u · v | u ∈ L und v ∈ S}.

Es seien ferner L₁, L₂ und L₃ drei formale Sprachen über A. Beweisen Sie, dass gilt:

L₁ · (L₂ · L₃) ⊆ (L₁ · L₂) · L_3.

Kann jemand die Aufgabe lösen und sie mir wenn möglich einigermaßen erklären? 

Comments

Was bedeutet der Punkt zwischen zwei Worten? Ist das die Konkatenation?

Answer 1

Die Behauptung \(L_1\cdot(L_2\cdot L_3)\subseteq (L_1\cdot L_2)\cdot L_3\) bedeutet:

\(\forall w\in L_1\cdot(L_2\cdot L_3)\Longrightarrow w\in (L_1\cdot L_2)\cdot L_3\) (das ist zu zeigen)

Sei \(w\in L_1\cdot (L_2\cdot L_3)\). Dann existiert ein \(u\in L_1\) und ein \(v\in L_2\cdot L_3\), sodass \(w=u\cdot v\). Ferner gibt es ein \(x\in L_2\) und ein \(y\in L_3\), sodass \(v=x\cdot y\). Daraus folgt: \(w=u\cdot (x\cdot y)\). Da die Konkatenation \(\cdot\) assoziativ ist (ggf. zu zeigen, falls ihr das in der Vorlesung noch nicht getan habt), gilt: \(w=u\cdot (x\cdot y)=(u\cdot x)\cdot y\) Es gilt \(u\cdot x\in L_1\cdot L_2\) und dadurch \((u\cdot x)\cdot y\in (L_1\cdot L_2)\cdot L_3\). Mit \(w=(u\cdot x)\cdot y\) folgt: \(w\in(L_1\cdot L_2)\cdot L_3\) \(\square\)