Questa prova per dimostrare che $ eq_ {cfg} $ è errata errata?

Question

Ho cercato prove che lo mostrano $ Eq_ {cfg} $ è riconoscibile in co-touring. Durante la ricerca di prove posso trovare solo prove sul modulo seguente:

Costruire un TM $ M $ che riconosce il complemento di $ Eq_ {cfg} $, M = "on input ⟨g, h⟩":

1. Per ogni stringa $ x in sigma^*$ in ordine lessicografico:
2. Testa se x ∈ L (g) e se x ∈ L (h), usando l'algoritmo per $ A_ {cfg} $ .
3. Se uno dei test accetta e gli altri rifiuti, accetta; altrimenti, continua. "

(Da: http://cobweb.cs.uga.edu/~potter/theory/6_rucibility.pdf)

Questa prova non è corretta?

Dì che la mia lingua è $ Sigma = {a, b } $ E che ho $ L (g_1) = {b } $ e $ L (g_2) = {bb} $. $ M $ dovrebbe accettare $ langle g_1, g_2 rangle $ da $ L (g_1) neq l (g_2) $. Ma se corriamo $ M $ insieme a $ langle g_1, g_2 rangle $ Il TM genererà prima $ x = a $, che non è in entrambe le lingue, quindi la macchina tornerà al passaggio 1 e quindi genera $ x = aa $, poi $ x = aaa $ E così via per sempre. La macchina non arriverà mai $ x = b $. Pertanto, la macchina passerà all'ingresso che dovrebbe accettare. Perciò $ M $ non è un riconoscimento di Turing.

La prova sarebbe corretta se il passaggio 1 invece indicherebbe "per ogni stringa $ x in sigma^*$, ordinato aumentando le dimensioni e poi Ordine lessicografico: "? Questo dovrebbe generare stringhe nel seguente ordine: $ x = a $, $ x = b $, $ x = aa $, $ x = ab $, $ x = ba $, $ x = bb $, $ x = aaa $, e così via. Quindi nel caso sopra $ M $ rifiuterebbe quando $ x = b $.