Fournit une grammaire sans contexte qui génère un langage de longueur impaire {w = 0 * 1 *: | w | est impair}

Question

Fournit une grammaire sans contexte qui génère le langage suivant sur

Σ = {0,1}: {w = 0 * 1 *: | w | est impair}

Ma solution:

S> AB | 0 | 1

A-> 0A |^

B-> 1B |^

Mais en utilisant cette grammaire nous sommes en mesure de créer un nombre pair de chaînes.

Je veux la grammaire qui produit L = {....} 0,1,000,111,001,011,00000,11111,00001,00011

Answer 1

Un nombre impair est la somme d'un nombre impair et un nombre pair, donc phrases les langues sont soit un nombre impair de 0 suivi d'un nombre pair de 1, soit un nombre pair de 0 suivi d'un nombre impair de 1. De plus, un nombre impair est un nombre pair plus un; si nous faisons cette substitution dans la description précédente, nous obtenons "un nombre pair de 0 suivi de 0 ou de 1 suivi d'un nombre pair de 1". Puisque chaque nombre pair est soit 0, soit deux de plus qu'un nombre pair, on se retrouve avec.

S -> A 0 B | A 1 B 
A -> ε | A 0 0 
B -> ε | B 1 1 

ou

S -> 0 | 1 | 0 0 S | S 1 1