pompage lemme pour CFG ne fonctionne pas

Question

Langue:

{(a^i)(b^j)(c^k)(d^l) : i = 0 or j = k = l} 

Nous prenons mot

w = a^0 b^n c^n d^n 

qui appartient évidemment à la langue parce que j = k = l

w = uvxyz

1. | vxy | < = n

2. | vy | > 1

et maintenant v et y peuvent être:

1. un caractère unique et si on pompe le caractère unique du mot ne soit plus dans la langue

2. deux personnages, compte du troisième sera plus bas donc le mot n'est pas dans la langue

Ainsi, la preuve que ce lan Le guage n'est pas CF n'est pas censé être faisable avec le lemme de pompage standard, juste avec le lemme d'ogdens, mais je ne comprends pas pourquoi la preuve ci-dessus est invalide.

Answer 1

Cela ne fonctionne pas car en fait chaque chaîne pompée est dans la langue, car vous n'avez toujours pas a s (c'est-à-dire, i = 0).

Et si vous choisissez une chaîne où i> 0, vous ne pouvez pas garantir que v est non seulement un certain nombre de a s et x est la chaîne vide.