Эквивалентные преобразования контекстно-свободных грамматик

Цель работы:

Закрепить понятия «эквивалентные грамматики», «приведенная КС-грамматика»; сформировать умения и навыки эквивалентных преобразований контекстно-свободных грамматик.

Задание на лабораторную работу

Разработать программное средство, автоматизирующее процесс эквивалентного преобразования КС-грамматик. Программное средство должно выполнять следующие функции:

1) организация ввода грамматики и проверка ее на принадлежность к классу КС-грамматик;

2) проверка существования языка КС-грамматики;

3) реализация эквивалентных преобразований грамматики, направленных на удаление:

а) бесполезных символов;

б) недостижимых символов;

в) e-правил;

г) цепных правил;

д) левой факторизации правил;

е) прямой левой рекурсии.