Дан язык SuperParanthesis
, состоящий из терминалов "(", ")" и "<>" (как один символ).
Скобочки выполняют привычную для всех группировку. "<>" закрывает все открытые скобочки.
Примеры слов в языке:
((()))
(()(()()<>
(<>()()()(((())<><><>
Это
не в языке:
(((<>)
Вопрос: Возможно ли написать context-free (контекстно-независимую?) грамматику для языка SuperParanthesis?
Желательно, отвечать аргументированно
.
ЗЫ. Вопрос теоретический, никаких вариантов "нет, но можно обойти" и т.п. не надо.
Свой вариант пока не привожу, т.к. не уверен, что он правильный, а сбивать вас с мысли не хочется.
С уважением,
fAX.
16.01.03 23:36: Перенесено из 'Алгоритмы'
...Complex problems have simple, easy-to-understand wrong answers...
(Grossman's Misquote of H.L.Mencken)