Parikhs Theorem: CFLs "enthalten" reguläre Sprachen?

Der erste Satz des Wikipedia-Artikels zu Parikhs Theorem lautet:

"Parikhs Theorem in der theoretischen Informatik besagt, dass die Sprache nicht von einer regulären Sprache zu unterscheiden ist, wenn man nur die relative Anzahl der Vorkommen von Terminalsymbolen in einer kontextfreien Sprache ohne Rücksicht auf ihre Reihenfolge betrachtet."

Ich habe Probleme, diesen Satz zu verstehen. Ich verstehe, dass unäre CFLs als die Vereinigung endlich vieler arithmetischer Sequenzen beschrieben werden können. Bedeutet dies, dass, wenn wir einen Morphismus auf eine CFL anwenden , die beispielsweise und für einige und für alle mit c \ neq a abbildet , dann ist h (L) eine unäre reguläre Sprache? Könnte jemand darauf näher eingehen?$h$$L$$a \longrightarrow a$$c \longrightarrow \epsilon$$a \in \Sigma$$c \in \Sigma$$c \neq a$$h(L)$

Das Parikh-Bild $\Psi$ eines Wortes ist ein Vektor, der die Nummer jedes Buchstabens im Alphabet zählt: zum Beispiel $\Psi( abbabaaca ) = (5,3,1)$ vorausgesetzt, das Alphabet ist $\{a,b,c\}$.

Das Parikh-Bild einer Sprache ist die Menge der Parikh-Bilder der Zeichenfolgen in der Sprache: $\Psi( \{a^nb^nc^n\mid n\ge 0 \}) = \{(n,n,n)\mid n\ge 0 \}$.

Der Satz besagt, dass die Parikh-Bilder kontextfreier Sprachen tatsächlich Parikh-Bilder regulärer Sprachen sind $\Psi( \{( ab)^n c^n\mid n\ge 0 \}) = \Psi( (abc)^*)$.

(In einer früheren Bearbeitung hatte ich das Beispiel $\Psi( \{a^nb^nc^n\mid n\ge 0 \}) = \Psi( (abc)^*)$. Technisch korrekt, aber der Leser wird feststellen, dass die Sprache nicht kontextfrei ist.)

Ich bin damit einverstanden, dass der Wortlaut auf Wikipedia nicht sehr klar ist, aber ich glaube, dass er sich auf die folgende Beziehung bezieht:

Nennen Sie zwei Wörter Buchstabenäquivalent, wenn sie gleich sind, wenn Sie die Reihenfolge der Zeichen außer Acht lassen. Das heißt: Die lexikografische Sortierung ihrer Zeichen (Beibehaltung von Duplikaten) ergibt dasselbe Wort. (Mit anderen Worten: Ihre Parikh-Bilder sind die gleichen.)

Nennen Sie zwei Sprachen Buchstabenäquivalent, wenn ihre Wörter sind, das heißt: lexikographisches Sortieren ihrer Wörter erzeugt dieselbe Sprache. (Mit anderen Worten: Ihre Parikh-Bilder sind die gleichen.)

Der Satz impliziert, dass jede kontextfreie Sprache ein Buchstabe ist, der einer regulären Sprache entspricht. Zum Beispiel,$\{ a^nb^n \mid n \geq 0\}$ ist ein Buchstabe äquivalent zu $(ab)^*$.

(Der Begriff Brief Äquivalent kann in zB gefunden werden Eine vereinfachte Nachweis von Parikh Theorem von J. Goldstine (1977) .)