Докажите, что язык не является контекстно-свободным, используя лемму прокачки - PullRequest
Новая
       51

Докажите, что язык не является контекстно-свободным, используя лемму прокачки

1 голос
/ 10 мая 2019

У меня есть следующий алфавит: Σ = {0, 1,.,,, 9} и Язык L , определенный как:

L = {abc |a + b = c}

, где подстроки a , b и c интерпретируются как обычные целые числа.

Мой ответ до сих пор :

Предположим, L не зависит от контекста.Тогда лемма прокачки для контекстно-свободных языков применяется к L .

Пусть n - константа, заданная леммой прокачки.

Let z = 10 ^ n20 ^ n30 ^ n явно z ∈ L и | z |≥ n

По лемме мы знаем, что z = uvwxy с n ≥ | vwx |и | VX |≥ 1

Существуют возможности ...

Мои вопросы:

Я вижу 8 возможностей, где vwx может находиться в пределах z.Например, в начале, включая 1 и перекрывающийся с начальным 0 ^ n.Еще один пример начального 0 ^ n.Это один из способов думать в этом конкретном вопросе?Как я могу прокачать и показать, что результат не принадлежит L?

Спасибо за ваше время.

1 Ответ

0 голосов
/ 22 мая 2019

Я думаю, что ваш выбор слова тоже работает, но я выберу более простое (для меня), чтобы показать то же самое. Вы, вероятно, можете адаптировать это к своему выбору строки.

Выберите w = (1 ^ p) (2 ^ p) (3 ^ p), где p из леммы прокачки для контекстно-свободных языков. Во-первых, обратите внимание, что 11 ... 1 + 22 ... 2 = 33 ... 3 - все числа имеют p цифр. Теперь есть ровно пять простых случаев для позиции vxy, если w = uvxyz:

  1. vxy состоит только из 1. В этом случае откачка (удаление хотя бы одного из 1) обязательно должна привести к появлению строки не на языке. Поскольку при добавлении любой цифры не может быть переноса, строка должна делиться на три части равной длины для a, b и c; они должны иметь точно такое же количество цифр. Таким образом, удаление 3k цифр с фронта тянет k из 2 в a, а 2k из 3 в b. Но тогда младшая значащая цифра a + b должна быть 5, которая не является символом в w.
  2. vxy состоит из 1 и 2. В этом случае откачка (удаление некоторого числа 1 и 2) обязательно должна привести к появлению строки не на языке. Поскольку при добавлении любой цифры не может быть переноса, строка должна делиться на три части равной длины для a, b и c; они должны иметь точно такое же количество цифр. Удаление цифр 3k из 1 и 2 должно привести к 3 в b. Поэтому наименьшая значащая цифра a + b будет по крайней мере 4 (поскольку w не содержит 0), а 4 не является цифрой в w.
  3. vxy состоит из 2. Аргумент здесь такой же, как и во втором случае выше.
  4. vxy состоит из 2 и 3. Накачка в этом случае должна в конечном итоге поставить 2 в a и b, чтобы цифры перекрывались, поэтому мы получаем ту же проблему 4/5 цифр, что и выше.
  5. vxy состоит только из 3. Опять же, подкачка в этом случае должна в конечном итоге поставить 3 в b, вызывая проблему 4/5 цифр.

Иллюстрация:

  1. w = 1 ^ p 2 ^ p 3 ^ p, откачка до 1 ^ (p-3) 2 ^ p 3 ^ p, a = 1 ^ (p-3) 22, b = 2 ^ (p- 2) 3, c = 3 ^ (p-1), наименее значимая цифра a + b равна 5, слишком высокая, не может быть правильной.
  2. w = 1 ^ p 2 ^ p 3 ^ p, откачка до 1 ^ (p-1) 2 ^ (p-2) 3 ^ p, a = 1 ^ (p-1), b = 2 ^ (p-2) 3, c = 3 ^ (p-1), снова наименее значимая цифра 4, слишком высокая.
  3. w = 1 ^ p 2 ^ p 3 ^ p, откачка до 1 ^ p 2 ^ (p-3) 3 ^ p, a = 1 ^ (p-1), b = 1 2 ^ (p- 3) 3, с = 3 ^ (р-1). Опять же, младшая цифра 4 слишком высокая.
  4. w = 1 ^ p 2 ^ p 3 ^ p, накачка до 1 ^ p 2 ^ (p + 1) 3 ^ (p + 2), a = 1 ^ p 2, b = 2 ^ p 3, с = 3 ^ (р + 1). Теперь наименее значимая цифра слишком высокая.
  5. w = 1 ^ p 2 ^ p 3 ^ p, накачка до 1 ^ p 2 ^ p) 3 ^ (p + 3), a = 1 ^ p 2, b = 2 ^ (p-1) 33 с = 3 ^ (р + 1). ЛСД все еще слишком высок.
...