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