0 Daumen
109 Aufrufe

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 L1, L2 und L3 drei formale Sprachen über A. Beweisen Sie, dass gilt:

L1 · (L2 · L3) ⊆ (L1 · L2) · L3.


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

Gefragt von

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

1 Antwort

+1 Punkt

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\)

Beantwortet von 6,8 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...