Грамматика для скобочек.
От: fAX Израиль  
Дата: 27.12.02 12:26
Оценка:
Дан язык 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)
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.