Редактировать: Я полностью вывел вас на неверный путь.Вот что происходит, когда я пытаюсь помочь, когда сам не решил проблему полностью.
Лемма Огдена
Предположим, что L не зависит от контекста.По лемме Огдена существует целое число p, которое имеет следующие свойства:
Если задана строка w в L длиной не менее p символов, где хотя бы p из этих символов «помечено», то w можно представить в видеuvxyz, которые удовлетворяют:
- x имеет по крайней мере один отмеченный символ,
- либо u и v оба имеют отмеченные символы, либо y и z оба имеют отмеченные символы,
- vxy имеет не более p отмеченных символов, и
- uv i xy i z находится в L для i> = 0
Это лемма Огдена.Теперь пусть q будет целым числом, делимым на каждое натуральное число, не превосходящее p.Пусть w = a p + q b p + q c p .Отметить каждый c.В # 2 u или v должны содержать хотя бы один c.Если либо u, либо v содержит какой-либо другой символ, то # 4 завершается ошибкой, поэтому u и v должны содержать только c.Но тогда # 4 терпит неудачу, когда i = q / | uv |.Мы знаем, что q делится на | uv |потому что p> | uv |> 0, и q делится на все натуральные числа меньше p.
Обратите внимание, что лемма Огдена превращается в лемму накачки, когда вы отмечаете все символы.
Лемма накачки
Предположим, что L не зависит от контекста.По лемме прокачки существует длина p (не обязательно такая же, как указано выше), так что любая строка w в L может быть представлена как uvxyz, где
- | vxy |<= p, </li>
- | vy |> = 1 и
- uv i xy i z находится в L для i> = 0.
Дана строка wв L либо m> n, либо m
Предположим, что m> n.(Обратите внимание, что Λ обозначает пустую строку.)
- Пусть u = a n b n c m-1
- Пусть v = c
- Пусть x = Λ
- Пусть y = Λ
- Пусть z = Λ
Предположим, что n> m.
- Пусть u = a n-1
- Пусть v = a
- Пусть x = Λ
- Пусть y = b
- Пусть z = b n-1 c m
Это показывает, что ни одна строка из L не обеспечиваетконтрпример, использующий лемму прокачки к предположению, что L является языком, не зависящим от контекста (даже если он чувствителен к контексту).