Минимизация синтаксических диаграмм с многовходовыми компонентами | Прикладная дискретная математика. 2018. № 41. DOI: 10.17223/20710410/41/9

Рассмотрена задача минимизации синтаксических диаграмм. Для её решения диаграммы Вирта (ДВ) преобразуются в синтаксические диаграммы с многовходо-выми компонентами (СД), которые по структуре совпадают с ДВ, но отличаются тем, что нетерминалы в нетерминальных вершинах заменяются начальными узлами соответствующих компонент. На множестве узлов СД вводится отношение, обладающее свойством эквивалентности, которое разбивает множество узлов на классы эквивалентности. Доказано, что «стягивание» класса эквивалентности в один узел является эквивалентным преобразованием. Если классу эквивалентности принадлежат узлы различных компонент, то в результате «стягивания» происходит соединение компонент в одну, которая имеет несколько входов. Предложены алгоритмы разбиения множества узлов на классы эквивалентности и построения СД. Приводится пример, показывающий, что построенная по предложенным алгоритмам СД значительно меньше эквивалентной ей ДВ.