Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ PRIKLADNAYa DISKRETN...arrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
PRIKLADNAYa DISKRETNAYa MATEMATIKA
Article . 2019 . Peer-reviewed
Data sources: Crossref
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
zbMATH Open
Article . 2019
Data sources: zbMATH Open
versions View all 2 versions
addClaim

This Research product is the result of merged Research products in OpenAIRE.

You have already added 0 works in your ORCID record related to the merged Research product.

MINIMIZATION OF CONTEXT-FREE GRAMMARS

МИНИМИЗАЦИЯ КОНТЕКСТНО-СВОБОДНЫХ ГРАММАТИК
Authors: Ryazanov, Yu. D.; Nazina, S. V.;

MINIMIZATION OF CONTEXT-FREE GRAMMARS

Abstract

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.

Keywords

Grammars and rewriting systems, formal language, formal grammar, minimization, Formal languages and automata, equivalence relation

  • BIP!
    Impact byBIP!
    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
Powered by OpenAIRE graph
Found an issue? Give us feedback
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).
BIP!Citations provided by BIP!
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.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
2
Average
Top 10%
Average
gold