Как вы разделяете строку в прокачке леммы?

Question

Например, докажем, что L = {0 ^ n1 ^ n | n ≥ 0} нерегулярно.

Чтобы доказать, что язык неправильный, опровергните любое из: (1) | uv | ≤ n (2) | v | ≥ 1 (3) для всех i ≥ 0: uviw ∈ L таких, что | Увиу | > = n

Предположим, что L регулярно, а затем по лемме накачки следуют приведенные выше правила. Теперь пусть x ∈ L и | x | ≥ п. Итак, по лемме накачки существует такое u, v, w, что выполняется (1) - (3).

Покажем, что для всех u, v, w, (1) - (3) нет hold.

Если (1) и (2) выполнены, то x = 0 ^ n1 ^ n = uvw с | uv | ≤ n и | v | ≥ 1.

// Как вы поделили строку языка? Как w = 0 ^ c1 ^ n?

Итак, u = 0 ^ a, v = 0 ^ b, w = 0 ^ c1 ^ n, где: a + b ≤ n, b ≥ 1, c ≥ 0, a + b + c = n

Спасибо, Рахман

Answer 1

Вы используете n для двух вещей: в определении языка, а также для константы леммы прокачки. Давайте использовать n_0 для константы. В вашем условии (iii) последнее утверждение должно быть |uvw| \geq n_0 без показателя степени i.

Теперь мы можем выбрать, например, слово a^{n_0}b^{n_0}, которое удовлетворяет этому требованию к длине. Из условия |uv|\leq n_0 мы непосредственно видим, что u и v состоят только из символов a для каждой факторизации, которая удовлетворяет условиям леммы накачки. Таким образом, любое слово в uv^iw для i>1 будет иметь a больше, чем b и, следовательно, не будет в языке, что противоречит условию номер три.