Minimization of context-free grammars
Prikladnaâ diskretnaâ matematika, no. 3 (2019), pp. 90-96

Voir la notice de l'article provenant de la source Math-Net.Ru

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, minimization.
Mots-clés : formal grammar, equivalence relation
@article{PDM_2019_3_a10,
     author = {Yu. D. Ryazanov and S. V. Nazina},
     title = {Minimization of context-free grammars},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {90--96},
     publisher = {mathdoc},
     number = {3},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2019_3_a10/}
}
TY  - JOUR
AU  - Yu. D. Ryazanov
AU  - S. V. Nazina
TI  - Minimization of context-free grammars
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2019
SP  - 90
EP  - 96
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2019_3_a10/
LA  - ru
ID  - PDM_2019_3_a10
ER  - 
%0 Journal Article
%A Yu. D. Ryazanov
%A S. V. Nazina
%T Minimization of context-free grammars
%J Prikladnaâ diskretnaâ matematika
%D 2019
%P 90-96
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2019_3_a10/
%G ru
%F PDM_2019_3_a10
Yu. D. Ryazanov; S. V. Nazina. Minimization of context-free grammars. Prikladnaâ diskretnaâ matematika, no. 3 (2019), pp. 90-96. http://geodesic.mathdoc.fr/item/PDM_2019_3_a10/