This article is cited in
2 papers
Mathematical Backgrounds of Informatics and Programming
Minimization of context-free grammars
Yu. D. Ryazanov,
S. V. Nazina Belgorod State Technological University named after V. G. Shukhov, Belgorod, Russia
Abstract:
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.
Keywords:
formal language, formal grammar, equivalence relation, minimization.
UDC:
519.766.2
DOI:
10.17223/20710410/45/10
Fulltext:
PDF file (581 kB)