Лемма о накачке для КС-языков: КС–язык или нет?

ЛЕММА О НАКАЧКЕ для КС-ЯЗЫКОВ: КС–ЯЗЫК ИЛИ НЕТ? Известна лемма о накачке для контекстно-свободных языков. По аналогии с леммой о накачке для регулярных языков данный результат может быть использован при доказательстве отсутствия контекстной свободности ряда языков методом «от противного». Теорема (лемма о разрастании). Для любого контекстно-свободного языка L существует натуральная константа p, называемая длиной накачки языка, такая, что произвольное слово ∈ L с α ≥ p допускает факторизацию в виде α = uvwxy, u,v,w,x,y∈ * , удовлетворяющую следующим условиям: 1. слова αi = uviwxiy ∈ L , i ∈ Z + , 2. vx ≠  , 3. vwx  ≤ p . В первом условии возникает серия слов αi,, получающихся из факторизации слова , которая в известном смысле объясняет термин «накачка» в данной ситуации. Лемма о накачке говорит о том, что КС-языки обладают некоторым свойством периодичности попадания в них слов и является лишь необходимым условием для свойства контекстной свободности формального языка. Рассмотрим приемы её использования с целью строгого доказательства того, что некоторые формальные языки не могут порождаться какой либо КС-грамматикой и некоторые другие свойства КС-языков. Пример. Доказать, что нерегулярный язык L = {an bn : n ≥ 0 и n не кратно 5} является контекстно-свободным языком. Решение. Рассмотрим следующие два языка: L1 = {w: w состоит из a,b и длина слов w кратнa десяти}, L2 = {anbn: n ≥ 0}. Пусть L1 ' - дополнение к L1. Ясно, что L = L1' ∩ L2. Легко видеть, что L1 является регулярным языком, так как можно легко построить конечный автомат с 10 состояниями, который принимает любую строку в этого языка. Так как L1 регулярен, то и L1' -регулярен, так как класс регулярные языки замкнут относительно взятия дополнения. Язык L2 является контекстно-свободным языком ( вот пример КС- грамматики: S  ASB | , которая его порождает). Таким образом, язык L = L1 '∩ L2 также контекстно-свободный язык, так как класс контекстно-свободных языков замкнут относительно пересечения с регулярными языками. В этом примере применялась не лемма о накачке, а некоторое свойство замкнутости класса КС-языков относительно операций над ними. Задача . Будет ли язык { 1k0i1i0j1j 0k | i, j,k> 0} над алфавитом {0,1} КСязыком? Решение. Следующая грамматика будет порождать этот язык S → 1A0 A→ 1A0 | В В → CC С → 0D1 D → 0D1 | . Этот факт усматривается из вида приведенных выше правил с использованием индукции по длине вывода. Детали доказательства мы опускаем. Задача . Будет ли язык L={w # х | w подстрока строки x, где x,w {0,1} *} КС-языком? Здесь  просто маркер. Решение. Ответ - нет. Предположим противное, полагая, что язык L КС-язык. Пусть длина накачки языка L равна р. Рассмотрим слово S = 0p1p # 0p1p, которое принадлежит языку. Если мы разложим слово S в uvwxy, как утверждается в лемме о накачке, то возможны три случая факторизации. • Если vwx содержится в первой половине строки S, то накачка даже один раз (то есть, рассмотрение строки uv2wx2y) даст нам строку, где первая половина длиннее второй половины, что означает, что она не может быть подстрокой второй половины слова. • Если vwx полностью содержится во второй половине, то после накачки (то есть, при рассмотрении строки uwy) окажется, что вторая половина будет короче, чем первая подстрока (поскольку | vwx |> = 1). В этом случае строка также не будет принадлежать данному языку. • Если же vwx совпадает с символом #, то должно быть так, что # содержится в w, иначе накачивание дало бы слишком много # символов. Поэтому либо v будет строкой длины 1 или х будет строкой длины 0 или оба (в этой ситуации следует учесть тот факт, что | vwx |  р). Если слово v является не пустой строкой, тогда накачивание даст левой половине больше 1чем правой, так что левая сторона не будет подстрокой правой строки. Если х не пустая строка из нулей, то накачка даст правой стороне меньше нулей и левая сторона не будет частью правой стороны. В любом случае, приходим к выводу, что независимо от того, как мы выбираем факторизацию возникает противоречие. Так что язык не может быть КС-языком. Задача . Является ли язык {0i1i0j1i | i, j> 0} КС-языком ? Решение. Ответ- нет. Предположим, что это не так. Пусть длина накачки равна р. Рассмотрим строку S = 0p1p01p, которая содержится в языке. Если мы разложим S в S = uvwxy как в утверждается в лемме о накачке, то соображения аналогичные тем, что были в предыдущем решении, показывают, что, если есть vwx с одиноким нулем между ними, то накачивание даст то, что слово не попадает в язык. С другой стороны, если vwx не имеет одинокого нуля, то накачка даст слово 0p1p1p, которое не находится в языке. Это противоречие показывает, что язык не является контекстно-свободным. Задача . Язык L = {0n1n0n1n | n  0} не является КС-языком. Решение. Допустим, что язык оказался КС-языком. Пусть р его длина накачки. Покажем, что достаточно длинное слово S = 0p1p0p1p не может правильно накачиваться. Пусть имеем факторизацию слова S = uvxyz. Если какое-либо подслово v или y будет содержать более одного типа символов алфавита, то слово S` = uv2xy2z уже не содержит символы в правильном порядке. Следовательно, S` ∉ L. Если и v и у содержат один тип символа алфавита, то uv2xy2z содержит цепочки 0 и 1 неравной длины. Следовательно, S` ∉L. В любом случае возникает противоречие с балансом вхождения символов после применения накачки. Задача . Будет ли следующий язык L = {0n # 02n# 03n | n > = 0} КСязыком? Решение. Ответ - нет. Пусть верно противное и р длина накачки для данного языка. Покажем, что слово S = 0p # 02p # 03p не может быть накачано корректным образом. Пусть S = uvxyz –факторизация слова, которая удовлетворяет условиям леммы о накачке. Ни слово v, ни слово у не могут содержать #, т.к., в противном случае, слово s` = uv2xy2z будет содержать более двух символов #. Поэтому, если разделить х на три сегмента по вхождениям #: 01p, 02p, 03p, то, по крайней мере, один из сегментов не содержится ни в v, ни в у из-за их длин. Следовательно, s` = uv2xy2z не принадлежит L, потому что 1: 2: 3 отношение для длин сегментов не поддерживается. Следовательно, s` ∉L. Поскольку слово не может быть накачиваться , то L не является КС-языком. Задача 1. Показать, что следующий формальный язык L над Σ = {a, b, c} не контекстно-свободный. L = {an bj ck : k = jn}. Задача 2. Показать, что следующий формальный язык L над Σ = {a, b} не контекстно-свободный L = {ww R a/w / : w {a,b}*} Задача 3. Использовать лемму о накачке, чтобы доказать, что язык не является контекстно-свободным L = {ai b2iai : i ≥ 0} Задача 4. Докажите, что язык L = { ai b2i cj: i,j ≥ 0} является контекстносвободным. Задача 5. Доказать, что язык L ={а п bn : n ≥ 0 и п не кратно 5} является контекстно-свободным языком. Проверить на наличие КС–свойства следующие языки. Задача 6. {1k 0i 1i 0j 1j 0k | i, j, k > 0} Задача 7. {w # х | w подстрока слова, где w, x в {0,1} *}. Задача 8. {0i1i 0j1i | i,j > 0} Задача 9. Дополнение к языку {(0n1n)m | m,n > 0}. Задача 10. Ll = {0N1N0N1N | N  0}. Задача 11. В = {0n # 02n # 0 3n | n  0}. Задача 12. Выяснить, какие из приведенных ниже языков не являются КСязыками: 1) {aibj ck | 0 ≤ i < j < k}; 2) {aibjck | 0 ≤ i = j = k} ; 3) {aibjck | 0 ≤ i = j, k ≥ 0, i ≠ k} ; 4) {aibjck | 0 ≤ i = j, k ≥ 0} .