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

8

Sei L eine reguläre Sprache.
Ist die Sprache L2={y:x,z  s.t.|x|=|z| and xyzL} 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 L2.

Tomer
quelle
"genaue Mitte" scheint zu suggerieren ? Das wird übrigens auch regelmäßig sein! |x|=|y|=|z|
Hendrik
Haben Sie das Zeug aus unserer Referenzfrage ausprobiert ?
Raphael

Antworten:

6

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 , tLn0AnsnsBntnts,tRs,tsei 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.st

L2=n0sAntBnRs,t.
s,t
Yuval Filmus
quelle
3

Let für einen DFA sein . ohne Verlust der Allgemeinheit . Wir konstruieren ein ε-NFA für folgendermaßen:L q S , q FQ N = ( Q { q S , q F } , Σ , Δ , q S , { q F } ) L 2D=(Q,Σ,δ,q0,F)LqS,qFQN=(Q{qS,qF},Σ,Δ,qS,{qF})L2

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:Dq0fFpk:q0=qk,0αk,1qk,1αk,2αk,iqk,iαk,i+1αk,nkqk,nkpk(i):qk,iαk,i+1qk,i+1αk,i+2αk,nkiqk,nki0ink2Δ

  • (qS,ε,qk,i) für alle wie obeni
  • (qk,nki,ε,qF) für alle wie obeni

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 wL(N)=L2wL(N)wpk(i)DixyxwyL|x|=|y|=iwL2NixyZugehörigkeit zu . für einige Formen .wpk(i)kw

Somit ist .L(N)=L2

ipsec
quelle
Da es unendlich viele Wege gibt, scheint die Bemerkung "Dies kann effektiv gemacht werden" eine Erklärung zu benötigen. Beachten Sie, dass es nicht unbedingt erforderlich ist, diese Eigenschaft zu verwenden. Siehe die Antwort von Yuval, die (für mich) eine "nicht effektive" Version desselben Arguments ist.
Hendrik
Du hast recht. Sie müssen Schleifen nicht zweimal berücksichtigen. Der nächste kritische Punkt scheint zu sein, dass einige zu , da beim Kombinieren der Pfade neue Pfade entstehen könnten. Sie sehen, ich habe meine Beweise nicht gründlich geprüft, aber ich glaube, all diese Probleme könnten gelöst werden. wpk(i)w
IPSec