Cette preuve est-elle montrée que $ eq_ {cfg} $ est-il incorrect de co-tugring-reconnaissable?

Question

J'ai cherché des preuves qui montrent que $ Eq_ {cfg} $ est co-tuant-reconnaissable. Lors de la recherche de preuves, je ne peux trouver des preuves que sur le formulaire suivant:

Construire un TM $ M $ qui reconnaît le complément de $ Eq_ {cfg} $, M = "sur entrée ⟨g, h⟩":

1. Pour chaque chaîne $ x in Sigma ^ * $ dans ordre lexicographique:
2. Tester si x ∈ L (g) et si x ∈ L (h), en utilisant l'algorithme pour $ A_ {cfg} $ .
3. Si l'un des tests accepte et que l'autre rejette, acceptez; Sinon, continuez.

(De: http://cobweb.cs.uga.edu/~potter/theory/6_reductibilité.pdf)

Cette preuve n'est-elle pas incorrecte?

Dire que ma langue est $ Sigma = {a, b } $ Et que j'ai $ L (g_1) = {b } $ et $ L (g_2) = {bb} $. $ M $ devrait accepter $ Langle G_1, g_2 Hangle $ puisque $ L (g_1) neq l (g_2) $. Mais si nous courons $ M $ avec $ Langle G_1, g_2 Hangle $ Le TM générera d'abord $ x = a $, qui n'est pas dans les deux langues, donc la machine reviendra à l'étape 1, puis générera $ x = aa $, alors $ x = aaa $ Et ainsi de suite pour toujours. La machine n'aura jamais $ x = b $. Par conséquent, la machine bouclera sur l'entrée qu'elle devrait accepter. Par conséquent $ M $ n'est pas un reconnaissance Turing.

La preuve serait-elle correcte si l'étape 1 indiquerait à la place "pour chaque chaîne $ x in Sigma ^ * $, commandé en augmentant la taille et ensuite Ordre lexicographique: "? Cela devrait générer des chaînes dans l'ordre suivant: $ x = a $, $ x = b $, $ x = aa $, $ x = ab $, $ x = ba $, $ x = bb $, $ x = aaa $, etc. Donc dans le cas ci-dessus $ M $ rejeterait quand $ x = b $.