@_prostoUser

Всем доброго времени суток! Передо мной встала задача:
"Задана контекстно-свободная грамматика, задается как два множества элементов, и набор правил. Способ задания грамматики не имеет значение, можно описывать ее в текстовом файле, например. Грамматика в нормальной форме Хомского - контекстно-свободная грамматика , в которой каждое правило имеет один из следующих трех видов:
S->e,A->a,A->BC
Стоит задача, заданную контекстно-свободную грамматику преобразовать к виду Хомского. "
Для реализации алгоритма я выбрал C#. Так же хочу отметить, что с грамматиками я столкнулся впервые, и не имею нужного фундамента знаний. В вики нашел следующий алгоритм:
1)Уберём длинные правила.
2)Удаление ε-правил.
3)Удаление цепных правил.
4)Удалим бесполезные символы.
5)Уберём ситуации, когда в правиле встречаются несколько терминалов.

Немного почитав о грамматиках, написал парсер для КС заданной с клавиатуры. Так же покончил с длинными правилами. И начал разбираться со вторым пунктом. Тут вошел в ступор, так как не понимаю зачем нам избавляться от ε-правил, в дальнейшем понял что дело именно в том что S-начальное состояния. Толком в этом не разобрался. НО это подтолкнуло меня убедиться в верности этого алгоритма, не найдя ничего на русском, я полез в искать информацию на других языках. Нашел много алгоритмов, все они разные(хотя,имеют пересечения с тем что я взял за основу), а так же меняется порядок действий.

Вопрос заключается в правильности выбранного алгоритма, и порядком его действий. Я бы с удовольствием разобрался сам, но времени на сдачу работы осталось совсем немного.

P.S. буду рад любым советам и комментариям, информации по данной задаче
P.S.S. прошу заранее понимать, что мой уровень владения темы поверхностный
Благодарю за внимание!

0

@_prostoUser

Алгоритм верный, задача решена спасибо за отсутствие ответов, я на вас не в обиде

0

@vantfiles

0

@_prostoUser

К счастью задача решена была в туже неделю, давно сюда не заходил

0