Polynoms Größe CFG, so dass jedes Endgerät in einem Wort auftritt, gerade Anzahl von Malen (großes Alphabet)

Question

Finden Sie eine kontextfreie Grammatik (CFG) für die Sprache L aller Worte, so dass jedes Endgerät in einem Wort gerade Anzahl von Malen über ein möglicherweise großes Alphabet S

tritt auf

Meine lange aproach ist (die einzige Nicht-End-S):

S ? e | SS

x ? S: S ? xSx

x, y ? S: S ? xxSyy | yySxx | xySxy | xySyx | yxSyx | yxSyx

Ist das richtig? Die Produktionen erzeugen richtigen Worten, sie alle Wörter erzeugen?

EDIT: Kann ein CFG über großes Alphabet beschreibt eine Sprache, wobei jedes Terminal erscheint gerade Anzahl von Malen

?

EDIT_2: Wenn es eine Lösung gibt, ist es möglich, Chomsky Normalform Polynom in | S | ?

Answer 1

Es gibt sogar eine reguläre Grammatik dies zu erreichen. Da jede reguläre Grammatik ist per Definition kontextfrei, die Antwort ist „Ja“. Es ist auch möglich, einen endlichen Automaten zu konstruieren, aber da sie eine Grammatik gefragt ...

Hier ist, wie: Rückruf, dass eine regelmäßige Grammatik Regeln der Form A erlaubt -> b C oder A -> b oder A -> epsilon, wobei A und C ist nicht-Terminals und b ist ein Terminal. Dies bedeutet im Wesentlichen, dass jeder Nicht-Terminal ein Terminal erzeugt und eine andere nicht-Endgerät, das den Rest der Zeichenfolge generieren; wir konnten alle nicht-Terminal codiert eine bestimmte Eigenschaft über die Saiten sagen, dass es erzeugt.

Betrachten wir nun alle Untergruppen des Alphabets Sigma. Da Sigma soll endlich sein, so ist die Menge von Teilmengen (Powerset). Lassen Sie die Menge von nicht-Terminals die Powerset von Sigma sein.

Starten Sie mit einer Regel: {} -> a {a} für jeden Terminal ein. Für jeden Nicht-Terminal X, fügen Sie die Regel X -> ein X- {a}, wenn a in X; oder X -> a X + {a}, wenn ein nicht in X (Ich schreibe schlampig + und - für Vereinigungs und Differenz hier).

Schließlich, fügen Sie {} -.> Epsilon (das leere Wort)

Die Grammatik codiert in seinen nicht-Anschlüssen genau die Sätze von Anschlüssen, die in einer ungeraden Anzahl erschienen sind und haben somit wieder „aufgehoben“ werden.