Если

Я застрял, решая следующее упражнение:

Докажите, что если зависит от контекста, а R регулярно, то L / R = { w ∣ ∃ x ∈ $L$$R$ (т.е.правый фактор) не зависит от контекста.$L / R = \{ w \mid \exists x \in R \;\text{s.t}\; wx \in L\}$

Я знаю , что должен существовать КПК , который принимает и DFA , который принимает R . Я сейчас пытаюсь объединить эти автоматы в КПК, который принимает правильный коэффициент. Если я могу построить это, я доказал, что L / R не зависит от контекста. Но я застрял в создании этого КПК.$L$$R$$L/R$

Вот как далеко я сделал это:

В комбинированном PDA состояния являются декартовым произведением состояний отдельных автоматов. И ребра - это ребра DFA, но только те, для которых в будущем может быть достигнуто конечное состояние исходного PDA L. Но не знаю, как записать это формально.

Вот подсказка.

Вам нужно, чтобы ваша машина изначально принимала часть слова из , потребляя ленту по ходу дела. Затем, ничего не потребляя, вам нужно найти какое-то слово из R , которое переведет машину в конечное состояние. Выбранное слово из R играет роль входного слова для второй половины вычисления.$L$$R$$R$

Очевидно, что недетерминизм будет играть роль, как и продукт между двумя машинами. Хитрость в формализации этого состоит в том, чтобы настроить продукт так, чтобы он учитывал тот факт, что вход поступает от не от входа.$R$

Я не уверен, к чему вы клоните с помощью декартового произведения; это симулирует оба автомата параллельно, что даст вам пересечение. Но вы хотите, чтобы он идентифицировал все слова в которые имеют суффикс из R ! На интуитивном уровне это так.$L$$R$

Предположим, что наш вход . Очевидно, мы не можем проверить все возможные продолжения (для принадлежности к R ), но только конечное их число. Комментарий Артема наиболее полезен здесь; мы предполагаем, каким будет суффикс x , и запускаем оба автомата на нем.$w \in \Sigma^*$$R$$x$

Пусть и A R - КПК для L и NFA для R соответственно. Построим автомат A следующим образом. На входе ш ∈ Е * , моделировать A L . После того, как ж потребляется, переход к модифицированному пересечения L , R из A L и A R , сохраняя состояние из A L . Теперь решите для каждого перехода недетерминированным образом, какой символ является следующим в виртуальном входе. Принять $A_L$$A_R$$L$$R$$A$$w \in \Sigma^*$$A_L$$w$$A_{L,R}$$A_L$$A_R$$A_L$$w$тогда и только тогда , когда оба компонента достигают конечного состояния одновременно, то есть , если ш имеет продолжение х , так что ж Купить ∈ L и X ∈ R .$A_{L,R}$$w$$x$$wx \in L$$x \in R$

Вы также можете использовать формальные грамматики. Видите ли вы, как вы можете получить в двух грамматиках параллельно? В общем, не ясно, как адаптировать чтобы вы могли справиться с суффиксами; с помощью нормальной формы Чомский помогает.$G_L$

Предположим, что и и G R даны в нормальной форме Хомского. Измените G L так , чтобы крайний правый нетерминал был различим и сделал его начальный символ новым начальным символом. Ввести для выделенных версий нетерминалов новые правила, которые приводят к грамматике, которая выводится в G L и G R параллельно (нетерминалы - это пары нетерминалов); если обе грамматики согласуются с символом терминала, удалите составной нетерминал. Таким образом, суффикс в G L удаляется тогда и только тогда, когда он может быть получен в G L и в G R , он остается$G_L$$G_R$$G_L$$G_L$$G_R$$G_L$$G_L$$G_R$ .$w \in L/R$

Я рекомендую использовать ответ Рафаэля, который гораздо проще понять, но вот альтернативный, использующий свойства замыкания вместо автоматов:

Пусть - язык. Мы хотим прочитать слово w , но спросим L, есть ли w x в языке. Итак, мы хотим создать новый язык из L, который х "стер". Мы можем сделать это, используя гомоморфизм, но он может удалить буквы из w . Решение: разделите алфавит на две части и используйте разные буквы для w и x .$L \subseteq A^{\ast}$$w$$L$$w x$$L$$x$$w$$w$$x$

Более формально:

1) Создайте слов из L , где каждая буква помечена как 0 или 1. 2) Пересекайте ее с обычным языком ( A × 0 ) ∗ ( R × 1 ) . Это сила , которые все-прийти до всех 1 - х, а вторая часть поступает от R . Точное значение × оставлено для читателя. 3) Заменить ( а , 0 ) → а и$L' \subseteq (A \times \{0,1\})^{\ast}$$L$
$(A \times {0})^{\ast} (R \times 1)$$R$$\times$
$(a,0) \to a$ . Используемые свойства замыкания: гомоморфное изображение, прообраз, пересечение с обычными языками. Преимущество: это доказательство работает для других семейств (например, замените контекстное на обычное).$(a,1) \to \varepsilon$