Minimization of context-free grammars | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2019. № 45. DOI: 10.17223/20710410/45/10

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) V (X → α ⇔ Y → β ∧ |α∣ = ∣β∣ ∧ ∀i (α(i) = = β(i) ∨(α(i), β(i)) ∈ E))} where X, Y are non-terminals, α, β are chains of terminal and non-terminals, possibly blank, α(i) is the i-th character in chain α, β(i) is the i-th character in chain β. 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 nonterminals 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.