Komplexität der halben Sprache

24

Für jede Sprache über Σ * definieren L 1 / 2 = { x Σ * : x y L , y Σ | x | } . In Worten, L 1 / 2 besteht aus allen x für die eine ist y gleich lang , so daß x y L .LΣ

L1/2={xΣ:xyL,yΣ|x|}.
L1/2xyxyL

Eine Übung in Sipser Buch fordert , dass zu zeigen , ist regulär , wenn L ist. Ich habe zwei unterschiedliche Lösungen gesehen, und beide beinhalten eine exponentielle Explosion von Zuständen.L1/2L

Frage: Kann jemand baut eine Familie von Sprachen , so dass die kanonischen Automaten für ( L n ) 1 / 2 sind deutlich (etwa exponentiell) größer als die für L ? Meine bisherigen Bemühungen erhöhen die Staatsgröße nur um + 1 !{Ln}(Ln)1/2L+1

Aryeh
quelle
1
Sie erwähnen nicht das offensichtliche Problem der DFA-Minimierung. Ich habe die Beweise nicht gesehen, aber vielleicht nehmen sie sie nicht in die Tat um. und eine nachträgliche DFA-Minimierung der Proofkonstruktion könnte den DFA erheblich vereinfachen ...?
vzn
5
Die Konstruktionen in den Proofs sind abstrakt und es ist überhaupt nicht klar, wie sie mit den Standardtechniken minimiert werden können.
Aryeh
Können Sie die beste Sprachfamilie veröffentlichen, die Sie gefunden haben?
Diego de Estrada
Dies ist nicht erforderlich, um Ihre Frage zu beantworten, aber es kann hilfreich sein, die Konstruktionen zu skizzieren. Eine andere Möglichkeit besteht darin, das Problem empirisch mit zufälligen FSMs anzugreifen
vzn

Antworten: