Das Schließen regulärer Sprachen wird unter bestimmten Kürzungsvorgängen geschlossen

Lassen $f : \mathbb{N} \to \mathbb{N}$eine ganzzahlige Funktion sein. Für eine Sprache$L$, definieren

$$f(L) = \{w \mid \exists x : |x| = f(|w|) \text{ and } wx \in L\}$$

Zum Beispiel wenn $f(n) = n$ Dies ist nur die "Halbierungs" -Operation, und es ist bekannt, dass reguläre Sprachen darunter geschlossen werden - gehen Sie einfach gleichzeitig vorwärts und rückwärts (wobei der Rückwärtsgang alle möglichen Pfade versucht, wie in der Teilmengenkonstruktion).

Laut HMU sind auch reguläre Sprachen unter Übernahme der Funktionen geschlossen $2n, n^2, 2^n$. Es ist leicht zu sehen$2n$oder eine beliebige lineare Funktion - ging einfach mit jeder Geschwindigkeit rückwärts. Wie kann das gemacht werden?$n^2$ oder $2^n$? Es scheint nicht machbar, nur die Geschwindigkeit zu erhöhen, da man sich dazu die Anzahl der bisher unternommenen Schritte merken müsste.

Können wir die Lösung auch anpassen, um einige allgemein ausreichende Bedingungen zu erhalten, unter denen $f$hat diese Eigenschaft? (Ich bezweifle, dass es notwendige und ausreichende Bedingungen gibt, würde mich aber gerne als falsch erweisen lassen)

Nimm einen DFA $\langle Q,q_0,F,\delta \rangle$ zum $L$. Für jeden Staat$q \in Q$, es ist bekannt, dass

$$N_q = \{ n : \delta(q,x) \in F \text{ for some $|x|=n$} \}$$ ist eine eventuell periodische Menge. In diesen Begriffen haben wir $$f(L) = \bigcup_{q \in Q} \{ w : \delta(q_0,w) = q \text{ and } |w|+f(|w|) \in N_q\}.$$ Ein paar einfache Argumente zeigen das $f$ist zulässig (die regulären Sprachen sind unter geschlossen$f$) wenn für jeden Modul $m$gibt es einen DFA $\langle Q',q'_0,\delta' \rangle$ über das Alphabet $\{0\}$ welches "berechnet" $|w|+f(|w|) \bmod m$in dem Sinne, dass bei Eingabe $0^n$können Sie sich erholen $n+f(n) \bmod{m}$ von $\delta'(q'_0,0^n)$. Dies geschieht wiederum für jeden Modul$m$, die Funktionszuordnung $n$ zu $n+f(n) \bmod{m}$ist schließlich periodisch. Schon seit$n \bmod{m}$ selbst ist periodisch, wir schließen daraus, dass:

Eine Funktion $f$ ist zulässig, wenn für alle $m$, die Funktion $\psi_{f,m}(n) = f(n) \bmod{m}$ ist schließlich periodisch.

Der chinesische Restsatz zeigt, dass es ausreicht, Werte von zu berücksichtigen $m$ Das sind Hauptmächte.

Alle Polynome sind eindeutig zulässig: wenn $f$ ist also ein Polynom $\psi_{f,m}$ hat Punkt $m$. Exponentialfunktionen$a^n$ sind auch zulässig: wenn $m=p^k$dann auch nicht $p \mid a$, in welchem ​​Fall $\psi_{f,m}$ ist schließlich Null oder $(p,a)=1$In diesem Fall zeigt die Formel von Euler dies $\psi_{f,m}$ hat Punkt $\varphi(m)$.

Ich bin mir nicht sicher, ob der Satz zulässiger Funktionen weiter charakterisiert werden kann - dies ist eine interessante Forschungsrichtung.