2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Доказательство однозначности контекстно-свободной грамматики
Сообщение01.12.2013, 13:05 
В курсе "Теория и реализация языков программирования", который ведется в моём ВУЗе, не предлагается никаких алгоритмов по доказательству однозначности КС-грамматики. Однако что делать, если стоит именно такая задача? Предположим, у нас есть КС-грамматика вида:

$\\S \to aB|aBS|bAS|bA \\
A \to bAA|a \\
B \to bBB|b$

которая, по всей видимости, однозначная (предположил потому, что именно так вопрос стоит в книге Серебрякова, в котором конечно много опечаток в заданиях, но контрпример сходу не подбирается)
Что с ней можно сделать такого, чтобы доказать её однозначность?

 
 
 
 Re: Доказательство однозначности контекстно-свободной грамматики
Сообщение01.12.2013, 16:37 
Edmonton в сообщении #794899 писал(а):
В курсе "Теория и реализация языков программирования", ..., не предлагается никаких алгоритмов по доказательству однозначности КС-грамматики. Однако что делать, если стоит именно такая задача?
Не хочу Вас огорчать, но
Педивикия Неоднозначная грамматика писал(а):
Общая задача определения, является ли грамматика неоднозначной, алгоритмически неразрешима.

Это я пока так. Я сейчас подумаю и м.б. напишу чего-нибудь...

-- Вс дек 01, 2013 13:43:19 --

А вроде как неоднозначна: берем и делаем в нужном месте $B\to bBB$, а потом можно любое из этих двух $B$ ветвить и потом превращать в $b$, но деревья будут разные.

 
 
 
 Re: Доказательство однозначности контекстно-свободной грамматики
Сообщение01.12.2013, 17:21 
Sonic86 в сообщении #795039 писал(а):
А вроде как неоднозначна: берем и делаем в нужном месте $B\to bBB$, а потом можно любое из этих двух $B$ ветвить и потом превращать в $b$, но деревья будут разные.


Согласен; чувствовал, что в задании опечатка, но контрпримера почему-то подобрать не смог, спасибо!

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group