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

10

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

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

Мартин Бергер
источник

Ответы:

12

Множество определенно не зависит от контекста, но я думаю, что оно может быть неоднозначным по своей природе: рассмотрим L = { a m b m c n d m , n 0 } { d a m b n c nm , n 0 }ппс(L) тогда p p c ( L ) включает в себя классический по сути неоднозначный язык L = { a m b m c nm , n 0 } { a m b n c nm , n 0 }

Lзнак равно{aмбмсNd|м,N0}{daмбNсN|м,N0},
ппс(L) и можно доказать, что p p c ( L ) также по своей сути неоднозначно по обычному аргументу (примените лемму Огдена к обоим a n + n ! b n c n и a n b n c n + n !, чтобы вывести существование двух различные деревья для a n + n ! b n + n ! c n + n ! ).
L'знак равно{aмбмсN|м,N0}{aмбNсN|м,N0},
ппс(L)aN+N!бNсNaNбNсN+N!aN+N!бN+N!сN+N!
Сильвен
источник
Спасибо. Это было проще, чем я. Как вы думаете, варианты проблемы (например, префиксы и постфиксы должны быть разделены (новыми символами) демонстрируют аналогичную потерю не двусмысленности?
Мартин Бергер,
Вы имеете в виду что-то вроде ? Тогда, начиная с L = { d a m b m c nm , n 0 } { e a m b n c nm , n 0 }, вы обнаружите, что $ a n + n ! б н + н ! c n + n !ппс$(L)знак равно{вес$|вес',весвес'L}{$вес|вес',вес'весL}Lзнак равно{daмбмсN|м,N0}{еaмбNсN|м,N0}$aN+N!бN+N!сN+N!имеет два различных дерева в любой грамматике для . Боюсь, что в настоящий момент у меня нет никакой идеи о том, как можно было бы (простым способом) изменить операцию p p c для обеспечения однозначности: потерянный в операции префикс или суффикс может иметь решающее значение для сохранения однозначности. ппс$(L)ппс
Сильвен
1
Да что-то подобное. Так как это не работает, мне придется изменить дизайн моего домена приложения. Большое спасибо за ваш вклад.
Мартин Бергер