Хорошо известно, что дополнение к зависит от контекста. Но как насчет дополнения ?
fl.formal-languages
context-free
domotorp
источник
источник
Ответы:
Все-таки КЛЛ, полагаю, с адаптацией классического доказательства. Вот эскиз.
Рассмотрим , являющийся дополнением к , со словами длиной не mod удалено.L={xyz:|x|=|y|=|z|∧(x≠y∨y≠z)} {www} 0 3
Пусть . Ясно, что - это CFL, так как вы можете угадать позицию и считать, что заканчивает после этого. Покажем, что .L′={uv:|u|≡3|v|≡30∧u2|u|/3≠v|v|/3} L′ p u p/2 L=L′
Следовательно, в это позиция: или, другими словами, позиция в . Это показывает, что .вес | ты | + | V | / 3=3р / 2+ | ш | / 3-p / 2= | ш | / 3+р, п Y U2 | ты | / 3= хп≠ уп= V| V | / 3
Если , то пусть будет первыми символами , так что равно ; это остальная часть . Тогда: следовательно, аналогично, .Yп≠ зп U 32( | w | / 3 + p ) вес U2 | ты | / 3 Yп v вес |u|+|v|/3=2|w|/3+p v|v|/3=zp
источник
Вот как я думаю о решении этой проблемы с помощью КПК. На мой взгляд, это интуитивно понятнее.
Слово не имеет формы если (i) (мод 3), который легко проверить, или (ii) существует некоторый входной символ который отличается от соответствующего символа который встречаетсяпозиции позже.x www |x|≢0 a b |w|
Мы используем обычный прием использования стека, чтобы поддерживать целое число , имея новый символ «дна стека» , сохраняя абсолютное значениев качестве количества счетчиков в стеке и sgn ( ) в зависимости от состояния КПК. Таким образом, мы можем увеличить или уменьшить , выполнив соответствующую операцию.t Z |t| t t
Цель состоит в том, чтобы использовать недетерминизм, чтобы угадать позиции двух сравниваемых символов, и использовать стек для записи , где - расстояние между этими двумя символами.t:=|x|−3d d
Мы выполняем это следующим образом: увеличиваем для каждого видимого символа, пока не будет выбран первый угаданный символ , и записываем в состояние. Для каждого последующего входного символа, пока вы не решите, что видели , уменьшите на ( для длины ввода и для расстояния). Угадайте положение второго символа и запишите, ли . Продолжайте увеличивать для последующих входных символов. Принять, если (определяется по сверху) и .t a a b t 2 1 −3 b a≠b t t=0 Z a ≠ b
Хорошая вещь об этом - то, что должно быть совершенно ясно, как распространить это на произвольные полномочия.
источник
Просто другая («ориентированная на грамматику») перспектива, чтобы доказать, что дополнением является CF для любого фиксированного использующего свойства замыкания.{wk} k
Прежде всего обратите внимание, что в дополнении всегда есть такое что . Мы сосредоточимся на и начнем с простой грамматики CF, которая генерирует:{wk} i wi≠wi+1 w1≠w2
Например, для имеем ,к = 3 L = {aб0 , а0б000 , а00б00000 , . , , } гL= {S→ a b 0 | X00 ,X→ 0X00 | 0 b 0 }
Затем примените замыкание при обратном гомоморфизме и объединение :
Первый гомоморфизм:φ ( 1 ) → a , φ ( 0 ) → b , φ ( 1 ) → 0 , φ ( 0 ) → 0
Второй гомоморфизм:φ'(0)→a,φ′(1)→b,φ′(1)→0,φ′(0)→0
Примените замыкание при циклических сдвигах к чтобы получить множество строк длины не имеющих форму :L′ kn wk
Наконец, добавьте обычный набор строк, длина которых не делится на , чтобы получить точное дополнение к :k {wk}
источник