Закрытие однозначных контекстно-свободных языков под префиксом и постфиксом.

Пусть будет контекстно-свободным языком. Определить , чтобы быть пре- и постфиксное замыканием , другими словами, содержит все «с префиксами и postfixes, и , следовательно сам по себе. Мой вопрос: если зависит от контекста и имеет не однозначную грамматику, то же самое верно для ? $L$ $ppc(L)$ $L$ $ppc(L)$ $L$ $L$ $L$ $ppc(L)$

Я считаю, что этот основной вопрос уже был бы решен в период расцвета теории языка, но я не смог найти подходящую ссылку.

fl.formal-languages automata-theory grammars context-free-languages Мартин Бергер
источник

Множество определенно не зависит от контекста, но я думаю, что оно может быть неоднозначным по своей природе: рассмотрим $\mathit{ppc}(L)$ тогда включает в себя классический по сути неоднозначный язык

L знак равно {a^{м} б^{м} с^{N} d | м, N \geq 0} \cup {d a^{м} б^{N} с^{N} | м, N \geq 0},

$L=\{a^mb^mc^nd\mid m,n\geq 0\}\cup\{da^mb^nc^n\mid m,n\geq 0\}\;,$

p p c (L)

$\mathit{ppc}(L)$

и можно доказать, что

также по своей сути неоднозначно по обычному аргументу (примените лемму Огдена к обоим

чтобы вывести существование двух различные деревья для

L^{'} знак равно {a^{м} б^{м} с^{N} | м, N \geq 0} \cup {a^{м} б^{N} с^{N} | м, N \geq 0},

$L'=\{a^mb^mc^n\mid m,n\geq 0\}\cup\{a^mb^nc^n\mid m,n\geq 0\}\;,$

p p c (L)

$\mathit{ppc}(L)$

a^{n + n!} b^{n} c^{n}

$a^{n+n!}b^nc^n$

a^{n} b^{n} c^{n + n!}

$a^nb^nc^{n+n!}$

a^{n + n!} b^{n + n!} c^{n + n!}

$a^{n+n!}b^{n+n!}c^{n+n!}$

Сильвен
источник

Спасибо. Это было проще, чем я. Как вы думаете, варианты проблемы (например, префиксы и постфиксы должны быть разделены (новыми символами) демонстрируют аналогичную потерю не двусмысленности?

Мартин Бергер,

Вы имеете в виду что-то вроде

? Тогда, начиная с

вы обнаружите, что

{p p c}_{$} (L) = {w $ ∣ \exists w^{'}, w w^{'} \in L} \cup {$ w ∣ \exists w^{'}, w^{'} w \in L}

$\mathit{ppc}_\$(L)=\{w\$\mid\exists w',\,ww'\in L\}\cup\{\$w\mid\exists w',\,w'w\in L\}$

L = {d a^{m} b^{m} c^{n} ∣ m, n \geq 0} \cup {e a^{m} b^{n} c^{n} ∣ m, n \geq 0}

$L=\{da^mb^mc^n\mid m,n\geq 0\}\cup\{ea^mb^nc^n\mid m,n\geq 0\}$

$ a^{n + n!} b^{n + n!} c^{n + n!}

$\$a^{n+n!}b^{n+n!}c^{n+n!}$ имеет два различных дерева в любой грамматике для

. Боюсь, что в настоящий момент у меня нет никакой идеи о том, как можно было бы (простым способом) изменить операцию

для обеспечения однозначности: потерянный в операции префикс или суффикс может иметь решающее значение для сохранения однозначности.

{p p c}_{$} (L)

$\mathit{ppc}_\$(L)$

p p c

$\mathit{ppc}$

Сильвен

Да что-то подобное. Так как это не работает, мне придется изменить дизайн моего домена приложения. Большое спасибо за ваш вклад.

Мартин Бергер

Закрытие однозначных контекстно-свободных языков под префиксом и постфиксом.

Ответы: