Контекстное преобразование грамматики

Question

Может кто-нибудь сообщить мне, если есть какое-либо программное обеспечение для преобразования Нормальная форма Хомского в Форма Бэкуса-Наура и наоборот?

Answer 1

Ну, нормальная форма Хомского и форма Бэкуса-Наура на самом деле не одно и то же, поэтому я так не думаю. Но если вы сообщите нам, для чего вам нужно это программное обеспечение, мы могли бы вам помочь.

Теперь, исходя из того, что вы спросили, я предполагаю, что вы хотите, чтобы какой-то код нормализовал грамматику BNF к нормальной форме Хомского. Насколько я знаю, такого программного обеспечения не существует, но возможно, что оно существует, при условии, что это задача, которая на самом деле выполнима в вычислительном отношении.

Но, если вы будете более конкретны в том, что вам действительно нужно, мы сможем дать вам полезный совет об этой задаче.

РЕДАКТИРОВАТЬ: После того, как я немного покопался в моих книгах, оказалось, что очень возможно сформулировать алгоритм преобразования произвольного CFG в нормальную форму Хомского. У меня нет фактического алгоритма или его сложности.

Answer 2

Может быть JFLAP сделает то, что вы ищете.

Я еще не использовал его сам, но его порекомендовал мне мой профессор автоматов.

Глядя на "Что такое JFLAP?" Похоже, что он может конвертировать из "CFG -> CNF", что звучит как то, что вы ищете.

Answer 3

Как было указано, мой первоначальный ответ, что BNF уже находится в CNF, был неверным. Вы можете преобразовать любую контекстно-свободную грамматику в CNF, как объяснено здесь (PDF). Процесс преобразования также иллюстрируется в Sipser 2nd Ed. страницы 106-109, если у вас есть доступ к нему. Я не знаю, существует ли существующее программное обеспечение, которое автоматизирует этот процесс (но, казалось бы, его было бы просто написать).