Beweisen, dass die Sprache regelmäßig oder nicht regelmäßig ist

Sei eine reguläre Sprache. Beweise das: $L$

$L_{+--}=\left\{w: \exists_u |u|=2|w| \wedge wu\in L\right\}$

$L_{++-}=\left\{w: \exists_u 2|u|=|w| \wedge wu\in L \right\}$

$L_{-+-}=\left\{w:\exists_{u,v} |u|=|w|=|v| \wedge uwv\in L\right\}$

sind regelmäßig und:

$L_{+-+}=\left\{ uv:\exists_w |u|=|w|=|v| \wedge uwv\in L \right\}$

ist nicht regelmäßig.

Scheint mir sehr schwer zu sein. Ich nehme an, 1-3 sind ähnlich (aber ich kann mich irren), aber ich weiß nicht, wie ich mich nähern soll. Die allgemeine Idee besteht normalerweise darin, die endliche Zustandsmaschine so zu modifizieren, dass eine andere Sprache akzeptiert. Aber diese Konstruktionen sind oft sehr raffiniert und ich kann sie mir immer noch nicht alleine einfallen lassen. $L$

regular-languages xan
quelle

mögliches Duplikat von Wie kann man beweisen, dass eine Sprache nicht regelmäßig ist?

Bartosz Przybylski

Ich bin mir nicht sicher, ob Ihre Aussagen richtig sind, da nach dem Myhill-Nerode-Theorem die ersten drei Sprachen unendlich viele Äquivalenzklassen haben! für das erste: nimm das i-te in und das (i + 1) -te Wort, dann kann man für jedes i wählen, um zu zeigen, dass es a gibt Wort, das die Klassen von und

w_{i}

$w_i$

L_{+ - -}

$L_{+--}$

w_{i + 1}

$w_{i+1}$

u_{i}

$u_i$

w_{i}

$w_i$

w_{i + 1}

$w_{i+1}$

trennt

@Fayez Was ist, wenn zum Beispiel ? Dann hat nur eine Äquivalenzklasse. Gehen Sie Ihren Beweis durch und sehen Sie, was schief geht.

L = Σ^{*}

$L=\Sigma^*$

L_{+ - -} = Σ^{*}

$L_{+--} = \Sigma^*$

Yuval Filmus

@Bartek und jeder andere, der zum Abschluss abstimmt: Bei der Hälfte der Frage geht es tatsächlich darum zu beweisen, dass bestimmte Operationen an Sprachen die Eigenschaft bewahren, regelmäßig zu sein.

Yuval Filmus

Antworten:

Hier ist ein Beweis dafür, dass die Sprache ist regulär. Es kann geändert werden, um anzuzeigen, dass die ersten drei auf Ihrer Liste regelmäßig sind. (Beachten Sie, dass ich in geändert .) Bei einem DFA für erstellen wir einen NFA für . Das erste, was die NFA tut, ist , einen Zustand erraten (einen Zug zu machen) , dessen beabsichtigte Semantik der Zustand ist, in dem der DFA für nach dem Lesen von endet . Es werden dann gleichzeitig zwei Kopien des DFA für , eine beginnend mit dem Startzustand und die andere beginnend mit . Beim Lesen eines Symbols $L_0 = \{ w : \exists_u |u|=|w| \land uw \in L \}$ $wu$ $uw$ $L$ $L_0$ $\epsilon$ $q$ $L$ $u$ $L$ $q$ $a$ bewegt es sich nach einem beliebigen Symbol im ersten und nach im zweiten. Ein Zustand akzeptiert, wenn sich die erste Kopie im Zustand und die zweite in einem akzeptierenden Zustand befindet. $a$ $q$

Betrachten Sie für die letzte die Sprache und schneiden Sie mit . $L= a^+ b^+ c^+$ $L_{+-+}$ $a^+ c^+$

Yuval Filmus
quelle

Das sehe ich nicht. , welche ist eindeutig eine reguläre Sprache. Aber ich nehme an, ich liege falsch :) Kannst du mir die richtige Richtung zeigen?

L = a^{+} b^{+} c^{+} \Rightarrow L_{+ - +} \cap a^{+} c^{+} = {a^{n} c^{m} : n + m \equiv_{2} 0}

$L=a^+b^+c^+ \Rightarrow L_{+-+} \cap a^+c^+=\left\{ a^n c^m: n+m\equiv_2 0 \right\}$

Xan

Ich habe es geschafft, Ihre Konstruktion von zu ändern und sogar Bewegungen zu entfernen, damit es eleganter wird (meiner Meinung nach). Also die ersten drei Probleme gelöst und danke dafür! :) Aber das einzige, worum ich Sie bitte, ist, das letzte und meine Bedenken im obigen Kommentar zu klären. Ich wäre sehr dankbar.

L_{0}

$L_0$

ε

$\varepsilon$

Xan

Wenn ich berechne, bekomme ich etwas anderes. Beachten Sie, dass jedes Wort in ein enthalten muss .

L_{+ - +} \cap a^{+} c^{+}

$L_{+-+} \cap a^+ c^+$

L

$L$

b

$b$

Yuval Filmus

Entschuldigung, aber ich weiß nicht, wie ich berechnen soll . Ich nehme an, das Ergebnis ist , was uns das gibt, was wir wollen, aber ich weiß einfach nicht, wie ich das rechtfertigen soll.

L_{+ - +} \cap a^{+} c^{+}

$L_{+-+}\cap a^+c^+$

{a^{n} c^{n} : n \in N}

$\left\{ a^n c^n: n\in\mathbb{N}\right\}$

Xan

Ok, ich kann jetzt sehen :-)

xan