верификатор сложения нерегулярный, а контекстно-свободный?

Как я могу показать, что следующий язык (не)контекстно-свободен? Аргумент, что это не регулярно, выглядит следующим образом.

введите здесь описание изображения

Я подозреваю, что этот язык не зависит от контекста... Причина, по которой я так думаю, заключается в том, что L = {an bm c{n+m | n,m >= 0} не зависит от контекста. Доказательство этому можно найти на

http://cg.scs.carleton.ca/~michiel/TheoryOfComputation/TheoryOfComputation.pdf (стр. 102 в pdf; стр. 94 в тексте)

Доказательство довольно длинное, и, вероятно, его можно доказать намного короче, используя эквивалентность с КПК (т. е. сначала помещая некоторый символ n "+" m раз в стек и, следовательно, снова удаляя его n+m раз). В любом случае, этот пример заставляет меня поверить, что мой исходный язык также должен быть контекстно-свободным. Тем не менее, я действительно не понимаю, как я могу аргументировать это.


regular-language context-free-grammar
person user1870864    schedule 16.12.2012    source источник
comment
Я думаю, что этот сайт SE лучше подходит для таких вопросов: cs.stackexchange.com   -  person hyde    schedule 15.03.2013

Ответы (1)


arrow_upward
2
arrow_downward

Нет, ваше предположение неверно!

Язык L = { x = y + z | where x, y, z are binary integers and x is the sum of y and z} не является контекстно-свободным языком (CFL).

Я пытаюсь объяснить.

Прежде всего, рассмотрим следующие примеры строк s на языке L.

110 = 100 + 10   
1110 = 1100 + 10  
:
111000 = 110000 + 1000

В моем объяснении LHS — это X, а RHS — Y + Z.

Что такое прокачка Lemma для CFL?
Если язык L контекстно-свободен, то существует некоторое целое число p ≥ 1 такое, что любая строка s в L с |s| ≥ с. (где p - "длина накачки" может быть записана как

s = uvxyz
with substrings u, v, x, y and z, such that
1. |vxy| ≤ p,
2. |vy| ≥ 1, and
3. uv nxy nz is in L for every natural number n.

Это определение | ≥ 1 и 3. uv nxy nz принадлежит L для любого натурального числа n.

Примечание: средняя часть s, vxy не больше, чем длина накачки p. (условие 1)

[РЕШЕНИЕ]:

Выберем строку s из L, удовлетворяющую условию |s| ≥ p

наше s равно 1m0q = 1m-10q + 10q , где q > p , m-1 > p

Теперь общая длина s равна 2m + 2q -1, что больше, чем p, и, конечно, для некоторых комбинаций натуральных чисел это неравенство возможно (я не включаю длину + и =, чтобы упростить объяснение)

Теперь наш s находится на языке и достаточно велик в соответствии с леммой о накачке для CFG.

А теперь сломай:

u vxy z = 1m0q = 1m-10q + 10во

Попробуйте найти v и y, чтобы прокачать и сгенерировать новую строку на языке L, но имейте в виду, что v и y не должны быть слишком далеко от p (согласно условию 1).

У вас нет выбора для v и y, чтобы вы могли генерировать новые строки на языке!

(Шаг 1): потому что, если вы решите увеличить 1, вы не сможете прокачать обе стороны, правую и левую, от =, потому что последний 1 на левой стороне находится на q (>p) до первого 1 правой стороны. . следовательно, невозможно генерировать новые строки на языке.

(Шаг 2): Предположим, вы хотите снова накачать 0. Невозможно одновременно увеличить 0 на левой и правой сторонах, потому что последние 0 на левой стороне в m-1 (>p) растягиваются до первой 0 на правой стороне .

(Шаг 3). Вы не можете прокачать комбинацию 111...000... в обе стороны. , попробуйте это, вы получите строку из языка L.

Попробуйте и другие варианты в рамках правил Pumping Lemma. вы не найдете правильный выбор для v и y.

[ОТВЕТ]

Итак, у него есть строка s в L, которая достаточно велика, и с ее помощью мы не можем генерировать новые строки в языке. это противоречит лемме о накачке для CFL, поэтому данный L не является CFL.

person Grijesh Chauhan    schedule 17.12.2012
comment
1^m0^q = 1^m-10^q + 10^q - Это ошибка? Это кажется неправильным. Например. если m=3, q=1, вы получите 1110 = 110 + 10, что неверно, правильная сумма будет 1000 = 110 + 10 - person GMA; 13.01.2019