Regelmäßigkeit der exakten Wortmitte aus einer regulären Sprache

Sei $L$ eine reguläre Sprache.
Ist die Sprache $L_2 = \{y : \exists x,z\ \ s.t.|x|=|z|\ and\ xyz \in L \}$ regelmäßig?

Ich weiß, dass es der Frage hier sehr ähnlich ist , aber der Haken ist, dass es keine einfache Teilzeichenfolge eines Wortes in einer regulären Sprache ist, sondern eine "exakte Mitte" - wir müssen das Präfix und die Suffixlänge zählen.

Daher gehe ich davon aus, dass es nicht regelmäßig ist, aber ich konnte keinen Weg finden, dies zu beweisen. Ich konnte mir auch keine Möglichkeit vorstellen, die NFA von so zu ändern $L$, dass akzeptiert wird $L_2$.

Hinweis: Betrachten Sie einige DFA für . Für jedes n ≥ 0 sei A n die Menge der Zustände s, so dass es ein Wort der Länge n gibt, das den DFA vom Anfangszustand zu s führt . Sei B n die Menge der Zustände t, so dass es ein Wort der Länge n gibt, das den DFA von t in einen akzeptierenden Zustand führt. Sie bieten nicht nur zwei Zustände s , t , ließ R s , $L$$n \geq 0$$A_n$$s$$n$$s$$B_n$$t$$n$$t$$s,t$$R_{s,t}$sei die (reguläre) Menge von Wörtern, die den DFA von nach t führen . Wir haben L 2 = ⋃ n ≥ 0 ⋃ s ∈ A n t ∈ B n R s , t . Da es für s , t nur endlich viele Möglichkeiten gibt , ist die Vereinigung tatsächlich endlich und so regelmäßig.$s$$t$

Let für einen DFA sein . ohne Verlust der Allgemeinheit . Wir konstruieren ein ε-NFA für folgendermaßen:L q S , q F ∉ Q N = ( Q ∪ { q S , q F } , Σ , Δ , q S , { q F } ) L $D = (Q, Σ, δ, q_0, F)$$L$$q_S, q_F \notin Q$$N = (Q ∪ \{q_S, q_F\}, Σ, Δ, q_S, \{q_F\})$$L_2$

Finden Sie jeden Pfad in von zu jedem . Für jeden solchen Pfad konstruiere die Pfade für (dh konstruiere alle „mittleren Teile“ des Pfades). Dies kann effektiv durchgeführt werden. Konstruieren Sie indem Sie alle diese Pfade zusammen kombinieren mit:$D$$q_0$$f ∈ F$$p_k: q_0 = q_{k,0} \xrightarrow{α_{k,1}} q_{k,1} \xrightarrow{α_{k,2}} … \xrightarrow{α_{k,i}} q_{k,i} \xrightarrow{α_{k,i+1}} … \xrightarrow{α_{k,n_k}} q_{k,n_k}$$p_k^{(i)} : q_{k,i} \xrightarrow{α_{k,i+1}} q_{k,i+1} \xrightarrow{α_{k,i+2}} … \xrightarrow{α_{k,n_k-i}} q_{k,n_k-i}$$0 \le i \le \frac{n_k}2$$Δ$

• $(q_S, ε, q_{k,i})$ für alle wie oben$i$
• $(q_{k, n_k-i}, ε, q_F)$ für alle wie oben$i$

$L(N)$ ist konstruktionsbedingt regelmäßig.

Beweisskizze, dass : Sei . Durch die Konstruktion wissen wir, dass mindestens mit einem der Pfade oben übereinstimmen muss . Jeder dieser Pfade gehört zu einem Pfad in , der ein zusätzliches Präfix und Suffix der Länge . Wählen Sie als das durch dieses Präfix beschriebene Wort und das durch das Suffix beschriebene. Wir finden, dass , mit . Mit einer ähnlichen Argumentation finden wir für jedes ein Weg in . Sei die Länge von und w ≤ L ( N ) w p ( i ) k D i x y x w y ≤ L | x | = | y | = i w ∈ L 2 N i x y w p ( i ) k k $L(N) = L_2$$w ∈ L(N)$$w$$p_k^{(i)}$$D$$i$$x$$y$$xwy ∈ L$$|x| = |y| = i$$w ∈ L_2$$N$$i$$x$$y$Zugehörigkeit zu . für einige Formen .$w$$p_k^{(i)}$$k$$w$

Somit ist .$L(N) = L_2$