Was kann ich über die Parikh-Karte einer CSL sagen?

Schreiben Sie als Parikh-Karte --ie, , wobei gibt an, wie oft in erscheint . Es ist bekannt , dass für ein CFL , ist ein semilinearer Satz (dies ist Parikh-Theorem). Einige andere interessante Dinge sind bekannt, aber ich habe nichts über die Parikh-Karte einer kontextsensitiven Sprache gefunden. Bestimmtes,Ψ ( w ) = { ( # σ ( w ) ) σ ∈ Σ | w ∈ L } # σ ( w ) σ w L Ψ ( L $\Psi$$\Psi(w) = \{(\#_\sigma(w))_{\sigma\in \Sigma}\vert w\in L\}$$\#_\sigma(w)$$\sigma$$w$$L$$\Psi(L)$

Was kann ich über oder wenn kontextfrei sind? Zum Beispiel, wenn ich , ist es möglich, dass es eine CFL so dass ? (oder jede andere 'zunehmende' Sequenz, die in konvergiert .)Ψ ( ˉ L 1 ) L 1 , L 2 ϕ ( L ) = { ∑ σ # σ ( w ) | w ∈ L } = { | w | | w ∈ L } L ϕ ( ˉ L ) = { n ! | n ∈ $\Psi(L_2 - L_1)$$\Psi(\bar{L}_1)$$L_1, L_2$$\phi(L) = \{\sum_\sigma \#_\sigma(w)\vert w\in L\} = \{|w| \vert w\in L\}$$L$$\phi(\bar{L}) = \{n!\vert n\in \mathbb{N}\}$$\hat{\mathbb{Z}}$

Zum zweiten Teil Ihrer Frage: Wenn Sie Ihre CFL als Satz aller ungültigen Berechnungen einer Turing-Maschine auswählen (siehe z. B. Kapitel 8.6 in der ersten Ausgabe von "Einführung in die Automatentheorie, Sprachen und Berechnung"). ), ist die Menge aller Codierungslängen zum Akzeptieren von Berechnungen vonM φ ( ¯ L ) M .$L$$M$$\phi(\overline{L})$$M$

Obwohl dies Ihre Frage nicht direkt beantwortet, können Sie diesen Ansatz verwenden, um recht komplizierte Mengen zu erstellen.