Theory of Languages

Density: A Measure of Derivation Complexity in a Context-Free Grammar

A. Ya. Dikovsky


Abstract: An exact (up to order) estimate is obtained for the growth of the signalizing density function for context-free (CF) grammars generating the set $L_0$ of all regular binary bracketed sequences, i.e., the set containing: a) sequence ( ); b) $(z_1z_2)$ for every $z_1,z_2\in L_0$; and c) no other chains.

UDC: 518.5, 681.142.2

Received: 27.05.1970
Revised: 29.09.1971

 English version: Problems of Information Transmission, 1972, 8:2, 151–160

Bibliographic databases:

• 
•