Minimization of syntax diagrams with multiport components | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2018. № 41. DOI: 10.17223/20710410/41/9

The minimization problem for syntax diagrams is considered. For this purpose, we transform the Wirth diagrams (WD) into syntax diagrams with multiport components (SD), which are similar to WD in their structure, but differ in the fact that the non-terminals in nonterminal nodes are replaced with the starting nodes of the corresponding components. On the set of SD nodes, we introduce a relation which possesses the equivalence property, dividing the set of nodes into equivalence classes. We prove that uniting an equivalence class into one node is an equivalence transformation. If an equivalence class includes the nodes of various components, then, as a result of uniting the class into one node, the components are united into one component, which has several inputs. The algorithms for dividing the set of nodes into equivalence classes and plotting a SD are suggested. The algorithm for dividing the set of nodes into equivalence classes is based on a serial partitioning of the set of nodes into subsets so that non-equivalent nodes fall into different subsets. After partitioning the set of nodes into equivalence classes, an SD is constructed. In the SD construction algorithm, for each equivalence class, the following actions are executed: only one node from the class is left in the SD, the remaining nodes of the class are deleted, and if some arc in the source diagram is going to the deleted node, then it is redirected to one of remaining nodes. We give an example which demonstrates that a SD plotted by the suggested algorithms is considerably smaller than the equivalent WD. The resulting SD, after minimization process, can be used to construct memory efficient programs for formal languages processing.