Вопрос о бесконтекстном языке (качающий лемму)
Я знаю, что это непосредственно не связано с программированием, но я задавался вопросом, знает ли кто-либо, как применить насосную лемму к следующему доказательству:
Покажите что L = {(a^n) (b^n) (c^m): n! =m} не является бесконтекстным языком
Я довольно уверен относительно применения насосных лемм, но этот действительно раздражает меня. Что Вы думаете?
1 ответ
Редактировать: Я полностью вел вас по ложному пути. Вот что происходит, когда я пытаюсь помочь, хотя сам не решил проблему полностью.
Лемма Огдена
Предположим, что 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,
- | vy | > = 1 и
- uv i xy i z находится в L для i> = 0.
Для строки w в L либо m> n, либо m <п. Предположим, что p = 2.
Предположим, что 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 является контекстно-свободным языком (даже несмотря на то, что он контекстно-зависимый).