Deux grammaires différentes sur un ensemble de sorties

Question

Pouvez-vous me donner deux grammaires différentes qui produisent le même ensemble de mots?

Illustration:

Etant donné une grammaire A et B sur l'alphabet {0,1}, si la grammaire A peut produire le mot 0.101.001, la grammaire B pourrait aussi bien. Si la grammaire B peut produire 0101111, alors la grammaire A pourrait aussi bien l'être. Et si la grammaire A ne peut pas produire 01001 alors B ne le peut pas. Mais la chose ici est que la grammaire A et B sont différentes l'une de l'autre, c'est-à-dire qu'elles utilisent des algorithmes totalement différents. Ensuite, l'ensemble des sorties qu'ils produisent n'est pas seulement un sous-ensemble approprié de l'autre. Cela signifie que leur ensemble correspondant de sorties doit avoir la même cardinalité. Probablement, ils sont de classe de complexité différente, mais cela n'a pas d'importance. Si vous le permettez, j'apprécierais grandement que vous me donniez des grammaires sur l'alphabet {0,1} exactement comme la machine classique de Turing.

Answer 1

Vous ne savez pas si c'est possible. Si A peut produire la sortie a, alors soit B contient directement soit b ou b 'plus court que a qui génère a. Le même argument s'applique alors à b (et b ') - il est soit directement dans A, soit il existe un' et a '' plus court que b dans A qui génère b. Itérer cet argument et finalement vous arrivez à un point où les éléments individuels sont de longueur 1, donc vous ne pouvez pas les décomposer plus loin, et vous devez avoir des éléments égaux dans A et B.

Answer 2

Est-ce que cette astuce est OK? Les chaînes de type 0*n1*m (par exemple, 000000111) peuvent être construits de gauche à droite:

A 
A -> 0A 
A -> B 
B -> 1B 
B -> {} 

droite à gauche:

B 
B -> B1 
B -> A 
A -> A0 
A -> {} 

de milieu:

AB 
A -> A0 
A -> {} 
B -> 1B 
B -> {}