
Summary: This paper solves the problem of transforming the initial context-free grammar (CF-grammar) without excess characters into equivalent CF-grammar with less complexity. To solve this problem, the following relation on the set of a CF-grammar non-terminals is introduced: \(E = \{(X,Y): (X=Y) \vee (X\to \alpha\Leftrightarrow Y\to \beta \wedge\vert \alpha \vert = \vert \beta \vert \wedge \forall i\,(\alpha (i) = \beta (i)\vee (\alpha (i), \beta (i))\in E))\}\) where \(X\), \(Y\) are non-terminals, \(\alpha\), \(\beta\) are chains of terminal and non-terminals, possibly blank, \( \alpha (i)\) is the \(i\)-th character in chain \(\alpha, \beta (i)\) is the \(i\)-th character in chain \(\beta \). It is proved that the relation \(E\) has the equivalence property and splits the set of non-terminals into equivalence classes. An algorithm is proposed for splitting a set of non-terminals into equivalence classes based on the method of sequential decomposition of the set of non-terminals into subsets so that non-equivalent non-terminals fall into different subsets. New CF-grammar is built on a set of non-terminals \(N\), which elements are representatives of equivalence classes. From the set of rules of the initial CF-grammar, the rules with the left parts belonging to the set \(N\) are chosen. If there is a non-terminal in the left side of any selected rule that does not belong to the set \(N\), then it is replaced by its equivalent non-terminal from the set \(N\). After such transformations in the CF-grammar, sets of identical rules may appear. From each set of identical rules, we leave only one rule. The result is a CF-grammar containing less rules and non-terminals than the initial CF-grammar. The paper provides an example of the implementation of the described transformations.
Grammars and rewriting systems, formal language, formal grammar, minimization, Formal languages and automata, equivalence relation
Grammars and rewriting systems, formal language, formal grammar, minimization, Formal languages and automata, equivalence relation
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
