Zeigen Sie dass REG unter Verbindung abgeschlossen ist

Question

Frage:

Gegeben seien ein Alphabet Σ und zwei Wörter u und w
über Σ, die von gleicher Länge n sein sollen, d.h. u = u1...un und w = w1...wn mit ui, wi ∈ Σ.

Dann sei die Verbindung von u und w definiert als
ver(u, w) := u1w1...unwn.
Für zwei Sprachen L und K sei die Verbindung von L und K definiert als
ver(L, K) = {ver(u, v) : u ∈ L und v ∈ K und |u| = |v|}.
Zeigen Sie dass REG unter Verbindung abgeschlossen ist, d.h. zeigen Sie dass wenn
zwei Sprachen L und K regulär sind, dann ist auch ver(L, K) regulär.

Code:

Ich habe leider keinen Einsatz wie die Aufgabe gelöst wird, für Hilfe bin ich dankbar

Answer 1

Für die normale Verkettung \(u.v = u_1\dots u_n.v_1\dots v_n\):

Seien \(u,v\in \Sigma\) mit \(u=u_1u_2\dots u_n;v=v_1v_2\dots v_n\) und \( \lvert u\rvert = \lvert v \rvert = n \).

Angenommen, \(L,K\in\operatorname{REG}\). Dann gibt es DEAs \(M_L=\{K_L; \Sigma; \delta_L; s_L;F_L\}\) und \(M_K=\{K_K;\Sigma;\delta_K;s_K;F_K\}\), für deren zugehörigen Sprachen \(\mathcal{L}(M_L)=L\) und \(\mathcal{L}(M_K)=K\) gilt. Dabei ist \(K\) die endliche Zustandsmenge von \(K\) oder \(L\), $$\delta\, :\, K\times \Sigma \to K$$ die Überführungsfunktion, \(s\in K\) der Startzustand und \(F\) die endliche Endzustandsmenge mit \(F\subseteq K\).

Jetzt können wir einen NFA \(M'=\{K';\Sigma;\Delta;s_L;F_K\}\) wie folgt bauen: \(K'=K_L\cup K_K\) ist die endliche Zustandsmenge. Die Überführungsfunktion besitzt die selben Transitionen wie \(M_L\) und \(M_K\). Wir fügen aber noch die Transitionen \(\forall l\in F_L: \begin{array}{c|c}&\epsilon \\\hline l&s_K\end{array}\) hinzu. Der Startzustand ist der Startzustand des ersten Automaten. Die Endzustandsmenge ist die Endzustandsmenge des zweiten Automaten. Wir haben also erfolgreich einen NFA mit \(\mathcal{L}(M')=\operatorname{ver}(L;K)\) erstellt. Den NFA können wir jetzt noch in einen DFA umwandeln (siehe hier), demnach ist \(\operatorname{ver}(L;K)\in \operatorname{REG}\).

Bei der vermischten Verkettung \(\operatorname{ver}(u,v)=u_1v_1\dots u_nv_n\):

Sei \(M_L=(K_L,\Sigma, \delta_L,s_L,F_L)\) und \(M_K=(K_K,\Sigma,\delta_K,s_K,F_K)\) zwei DEAs die die Sprachen \(L\) und \(K\) erkennen.
Wir erstellen zuerst ein NEA \(N=(K,\Sigma, \delta,s,F)\) wie folgt:

• \(K=(K_L\times K_K) \)
• \(s=(s_K,s_L)\)
• \(F=(F_L\times F_K)\)
• \((\delta_L(x,l),y) \in \delta((x,y),l)\) Wenn der aktuelle Zustand von \(M_L\) zum Beispiel \(x\) ist und der von \(M_K\) \(y\) ist, dann wird beim Einlesen vom Zeichen \(l\) (notiert mit \(\delta((x,y),l)\)) der Zustand von L geändert zu \(\delta_L(x,l)\) während der aktuelle Zustand von \(K\) nicht geändert wird.
• Analog dann für \((x,\delta_K(y,l))\in\delta((x,y),l)\). (siehe NTHU CS oder Constructing a NFA for the following language)

Jetzt wandeln wir den NEA zum DEA um und sind fertig.

Comments

No front, aber hast du nicht einfach einen Automaten erstellt, der erst ein Wort aus L und dann ein Wort aus K erkennt?

---

Ja, das ist ja genau \(\operatorname{ver}(L,K)=\{u_1u_2\dots u_nv_1v_2\dots v_n | u\in L \land v \in K\}\)

---

Tja, dann hast du die Frage nicht richtig durchgelesen...

Guck dir die Definition von ver(L,K) genauer an...

---

Genau das habe ich gezeigt. Eine Sprache \(L\) ist genau dann regulär, wenn es einen DEA \(M\) gibt mit \(\mathcal{L}(M)=L\). Diesen Automaten habe ich hier kontruiert.

---

Mein Problem ist nur eben, dass $$ver(w,v)$$ mit $$w=w_1w_2...w_n, v=v_1v_2...v_n$$ nicht die Verkettung von Wörtern ist. Die Definition von Hassan war:

$$ver(w,v)= w_1v_1w_2v_2...w_nv_n$$LG Hartin Mils :)

---

Du hast vollkommen Recht, ich habe das überlesen und angenommen, dass es die normale Verkettung und keine vermischte Verkettung wäre.

So ändert sich das ganze wie folgt:

Sei \(M_L=(K_L,\Sigma, \delta_L,s_L,F_L)\) und \(M_K=(K_K,\Sigma,\delta_K,s_K,F_K)\) zwei DEAs die die Sprachen \(L\) und \(K\) erkennen.

Wir erstellen zuerst ein NEA \(N=(K,\Sigma, \delta,s,F)\) wie folgt:

\(K=(K_L\times K_K) \)

\(s=(s_K,s_L)\)

\(F=(F_L\times F_K)\)

\((\delta_L(x,l),y) \in \delta((x,y),l)\) Wenn der aktuelle Zustand von \(M_L\) zum Beispiel \(x\) ist und der von \(M_K\) \(y\) ist, dann wird beim Einlesen vom Zeichen \(l\) (notiert mit \(\delta((x,y),l)\)) der Zustand von L geändert zu \(\delta_L(x,l)\) während der aktuelle Zustand von \(K\) nicht geändert wird. Analog dann für \((x,\delta_K(y,l))\in\delta((x,y),l)\). (siehe NTHU CS oder Constructing a NFA for the following language)

Jetzt wandeln wir den NEA zum DEA um und sind fertig.

---

Danke dir, dann sind wir uns jetzt ja einig... Und Hassan ist dankbar für seine Hilfe :)

LG Hartin

---

Ja, genau :) Danke für den Hinweis.