Diskretnaya Matematika, Tome 12 (2000) no. 4, pp. 99-108
Citer cet article
N. Yu. Demin. On the number of rules needed for an automaton grammar to generate a finite language. Diskretnaya Matematika, Tome 12 (2000) no. 4, pp. 99-108. http://geodesic.mathdoc.fr/item/DM_2000_12_4_a7/
@article{DM_2000_12_4_a7,
author = {N. Yu. Demin},
title = {On the number of rules needed for an automaton grammar to generate a finite language},
journal = {Diskretnaya Matematika},
pages = {99--108},
year = {2000},
volume = {12},
number = {4},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/DM_2000_12_4_a7/}
}
TY - JOUR
AU - N. Yu. Demin
TI - On the number of rules needed for an automaton grammar to generate a finite language
JO - Diskretnaya Matematika
PY - 2000
SP - 99
EP - 108
VL - 12
IS - 4
UR - http://geodesic.mathdoc.fr/item/DM_2000_12_4_a7/
LA - ru
ID - DM_2000_12_4_a7
ER -
%0 Journal Article
%A N. Yu. Demin
%T On the number of rules needed for an automaton grammar to generate a finite language
%J Diskretnaya Matematika
%D 2000
%P 99-108
%V 12
%N 4
%U http://geodesic.mathdoc.fr/item/DM_2000_12_4_a7/
%G ru
%F DM_2000_12_4_a7
We consider the problem on reconstructing the data communication protocol, on the base of the message traffic. Formally, this problem is reduced to the problem to synthesise a grammar, given the language which it generates. We give a bound for the number of rules needed for the automaton grammar to generate a language of the given finite cardinality.
