RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2000 Volume 12, Issue 4, Pages 99–108 (Mi dm350)

On the number of rules needed for an automaton grammar to generate a finite language

N. Yu. Demin


Abstract: 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.

UDC: 519.7

Received: 18.11.2000

DOI: 10.4213/dm350


 English version:
Discrete Mathematics and Applications, 2000, 10:6, 587–596

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024