dimensione polinomiale CFG tale che ciascun terminale in una parola ricorre numero pari di volte (grande alfabetico)

Question

Trova una grammatica context-free (CFG) per il linguaggio L di tutti parole tale che ciascun terminale in una parola si verifica numero pari di volte in un possibilmente grande alfabeto S

La mia lunga aproach è (l'unico non terminale è S):

  

S ? e | SS

     

x ? S: S ? xSx

     

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

È corretto? Le produzioni generano parole corrette, si generano tutte le parole?

EDIT: Può un CFG su grande alfabeto descrivere un linguaggio, dove ogni appare terminale anche numero di volte

?

EDIT_2: se esiste una soluzione, è possibile Chomsky forma normale essere polinomiale in | S | ?

Answer 1

C'è anche una grammatica regolare per raggiungere questo obiettivo. Dal momento che ogni grammatica regolare è per definizione al contesto libero, la risposta ist "sì". E 'anche possibile costruire un automa a stati finiti, ma dal momento che lei ha chiesto per una grammatica ...

Funziona: richiamo che una grammatica regolare permette regole della forma A -> b C o A -> B o A -> epsilon, dove A e C sono non-terminali e b è un terminale. Questo essenzialmente significa che ogni non terminale genera un terminale e un altro terminale che non genererà il resto della stringa; potremmo dire che ogni codifica non terminali una certa proprietà sulle corde che genera.

Consideriamo ora tutti i sottoinsiemi dell'alfabeto Sigma. Poiché Sigma dovrebbe essere finita, così è l'insieme di sottoinsiemi (Powerset). Lasciare l'insieme dei non-terminali sia la powerset di Sigma.

Inizia con una regola: {} -> a {a} per ogni terminale. Per ogni X non terminale, aggiungere la regola X -> un X {a} se a è in X; o X -> a X + {a} se una non è in X (Sto scrivendo sloppily + e - per l'unione set e differenza qui).

Infine, aggiungere {} -.> Epsilon (la parola vuota)

I codifica grammatica nei suoi non-terminali esattamente i gruppi di terminali che sono apparsi in un numero dispari, e quindi devono essere "cancellato" di nuovo.