Behauptung: L▽R := {xuy | xy ∈ L, u ∈ R} ist nicht regulär.

Question

L▽R := {xuy | xy ∈ L, u ∈ R}

Sei L = L((ac)^+) und R = L(b^+)

Ich würde behaupten, dass die Sprache nicht regulär ist, da sich der zugehörige DFA immer merken müsste(wenn x = a und y = c ist) wie viele as auf der linken Seite sind und wie viele rechte cs dann entsprechend auf die rechte Seite müssten, aber sobald ein DFA sich etwas merken müsste, kann die vorliegende Sprache keine reguläre Sprache sein, zumindest habe ich das bisher so verstanden.

Answer 1

L▽R := {xuy | xy ∈ L, u ∈ R}

Wenn L und R regulär sind, dann ist L▽R regulär.

Sei L = L((ac)^+) und R = L(b^+)

L und R sind regulär.

da sich der zugehörige DFA immer merken müsste ... wie viele as auf der linken Seite sind

Die Sprache L besteht aus den Wörtern, die mit a anfangen, mit c enden und in denen sich a und c abwechseln.

Damit muss sich der DFA von L▽R nur merken, ob er nach einem a in den DFA von R abbiegt oder nach einem c.

Comments

Also gilt, dass L▽R für beliebige reguläre Sprachen L und R regulär ist ? Und wie lässt sich das hier am besten beweisen, kann man irgendwie einen DFA konstruieren?

---

Ein DFA \(A_L\) für \(L\) habe \(n\) Zustände, \(\{q_1,\dots,q_n\}\).

Der wird kopiert zum DFA \(A'_L\), die Kopie habe die Zustände \(\{q'_1,\dots,q'_n\}\).

Außerdem werden \(n\) Kopien \(A_{R,i}\) des DFA für \(R\) angelegt (\(i\in \{1,\dots,n\}\)).

Die DFAs werden nun wie folgt miteinender verdrahtet:

1. Von jedem Zustand \(q_i\) des DFA \(A_L\) führt eine \(\varepsilon\)-Transition zum Startzustand des DFA \(A_{R,i}\).
2. Von jedem Endzustand eines DFA \(A_{R,i}\) führt eine \(\varepsilon\)-Transition zum Zustand \(q'_i\) des DFA \(A'_{L}\).

Du musst dir noch darüber Gedanken machen, was der Startzustand und die Endzustände des so erzeugten Automaten sein sollen.

---

Der Startzustand des DFA AL wäre der Startzustand des NFAs

und der Endzustand von A'L wäre der Endzustand des NFAS?

---

und der Endzustand von A'L wäre der Endzustand des NFAS?

Besser gesagt die Endzustände von ...