Накачивание леммы для доказательства того, что язык не является регулярным

Привет, я пытаюсь делать практические вопросы для прокачки леммы. Мне нужно доказать, что язык L = {w E алфавит a,b,c | в w вдвое больше bs и вдвое больше bs, чем cs}

Теперь я создал слово w = a^4n * b^2n * c^n, которое принадлежит L. Я продолжаю пытаться продолжить вычисления, но не понимаю, что делать. Как узнать, что представляют собой xyz? И как доказать, что есть противоречие? Я пытался целую вечность и искал по всему Интернету, но я действительно борюсь.


pumping-lemma
person ArronK    schedule 25.02.2017    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Вот лемма о накачке для контекстно-свободных языков:

Если язык L является контекстно-свободным, то существует некоторое целое число p ≥ 1 (называемое «длиной накачки») такое, что каждая строка w в L, имеющая длину p или более символов (т. е. с |w| ≥ p) можно записать как

w = uvxyz с подстроками u, v, x, y и z, такими, что

  1. |vxy| ≤ р,
  2. |вы| ≥ 1 и
  3. u(v^i)x(y^i)z находится в L для всех i ≥ 0.

Взято из википедии

Давайте посмотрим на строку w=(a^4p)(b^2p)(c^p)

Чтобы показать противоречие, мы должны показать, что для каждой подстроки w накачивание слова удалит его из языка.

Рассмотрим несколько случаев:

  1. vxy (или в вашем случае вы пометили его как «xyz») содержит последовательность из 1 буквы (допустим, буква a, поэтому последовательность ^k, где k>=1). В этом случае, если вы накачаете строку для i=2, например, вы получите: u(v^2)x(y^2)z=uvvxyyz=(a^(4p+|vy|))(b^2p) (c^p), что не является словом языка, потому что 4p+|vy| больше, чем 2*2p (as в два раза больше, чем bs).

  2. vxy содержит последовательность из 2 букв (предположим, что за буквами as следует bs, поэтому последовательность (a^k)(b^l) k,l >= 1). В этом случае, если вы накачаете строку для i=2, вы получите: u(v^2)x(y^2)z=uvvxyyz=(a^(4p+|vy|))(b^(2p+|vy |))(c^p), что не является словом языка, потому что 2p+|vy| больше, чем 2*p (bs в два раза больше, чем cs)

Вы можете показать, что для каждой буквы a, b или c накачка с первым регистром удалит слово из языка, а для каждой последовательности из 2 букв (a^k)(b^l) или (b^k)(c^l) накачка со вторым регистром удалит слово из языка.

Из-за условия, что |vxy| ≤ p, мы не можем получить последовательность из 3 букв. Самая короткая подстрока, которую мы можем получить из 3 букв: a(b^2p)c с длиной 2p+2, которая не подходит для этого условия.

Таким образом, мы показали, что для каждой выбранной нами подстроки перекачивание слова приведет к его удалению из языка. Мы получили противоречие, что этот язык квалифицирует лемму о накачке, поэтому этот язык не является контекстно-свободным языком.

person Ron537    schedule 25.02.2017
comment
По-видимому, часто упускаемой из виду деталью является тот факт, что утверждение в пункте 3 включает ноль, что соответствует сжатию сконструированного слова, удовлетворяющего свойствам. Итак, в сумме можно было бы рассуждать также следующим образом. Поскольку длина vxy не превышает p, оно не может содержать более двух разных букв (либо только a, a и b, b и c, только c), поэтому, уменьшив его, мы получим uxz, в котором число либо только одного или две, но не три буквы уменьшились. uxz есть в языке, но не удовлетворяет его определяющему свойству - противоречию. - person Codor; 25.02.2017