Контекстно-свободный языковой вопрос (лемма о накачке)

Question

Я знаю, что это не имеет прямого отношения к программированию, но мне было интересно, знает ли кто-нибудь, как применить лемму о накачке к следующему доказательству:

Покажи то L={(a^n)(b^n)(c^m) :п!=м} не является контекстно-свободным языком

Я довольно уверенно применяю леммы о накачке, но эта меня очень раздражает.Что вы думаете?

Answer 1

Редактировать:Я совершенно вел вас по неверному пути.Вот что происходит, когда я пытаюсь помочь, хотя сам не до конца решил проблему.

Лемма Огдена

Предположим, что L является контекстно-свободным.По лемме Огдена существует целое число p, обладающее следующими свойствами:

Учитывая строку w в L длиной не менее p символов, где как минимум p из этих символов «отмечены», w можно представить как uvxyz, что удовлетворяет:

1. x имеет хотя бы один отмеченный символ,
2. либо u и v оба имеют отмеченные символы, либо y и z оба имеют отмеченные символы,
3. vxy имеет не более p отмеченных символов, и
4. ты в^я х у^я 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, где

1. | vxy | <= p,
2. | vy | > = 1, и
3. ты в^я х у^я 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 = b^n-1 с^м

Это демонстрирует, что ни одна строка из L не дает контрпримера с использованием леммы о накачке предположению, что L является контекстно-свободным языком (даже несмотря на то, что он контекстно-зависим).