We introduce the notion of a differentiation function of a context-free grammar which gives the number of terminal words that can be derived in a certain number of steps. A grammar is called narrow (or -narrow) iff its differentiation function is bounded by a constant (by ). We present the basic properties of differentiation functions, especially we relate them to structure function of context-free languages and narrow grammars to slender languages. We discuss the decidability of the equivalence of grammars with respect to the differentiation function and structure function and prove the decidability of the -narrowness of context-free grammars. Furthermore, we introduce languages representing the graph of the differentiation and structure function and relate these languages to those of the Chomsky hierarchy.
@article{ITA_2004__38_3_257_0,
author = {Dassow, J\"urgen and Mitrana, Victor and P\u aun, Gheorghe and Stiebe, Ralf},
title = {On differentiation functions, structure functions, and related languages of context-free grammars},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
volume = {38},
year = {2004},
pages = {257-267},
doi = {10.1051/ita:2004013},
mrnumber = {2076403},
zbl = {1082.68049},
language = {en},
url = {http://dml.mathdoc.fr/item/ITA_2004__38_3_257_0}
}
Dassow, Jürgen; Mitrana, Victor; Păun, Gheorghe; Stiebe, Ralf. On differentiation functions, structure functions, and related languages of context-free grammars. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 38 (2004) pp. 257-267. doi : 10.1051/ita:2004013. http://gdmltest.u-ga.fr/item/ITA_2004__38_3_257_0/
[1] and, The algebraic theory of context-free languages, in Computer Programming and Formal Systems, edited by P. Braffort, D. Hirschberg. North-Holland, Amsterdam (1963) 118-161. | Zbl 0148.00804
[2] , Eine neue Funktion für Lindenmayer-Systeme. EIK 12 (1976) 515-521. | Zbl 0348.68047
[3] , Numerical parameters of evolutionary grammars, in Jewels are forever, edited by J. Karhumäki, H. Maurer, Gh. Păun, G. Rozenberg. Springer-Verlag, Berlin (1999) 171-181. | Zbl 0944.68088
[4] and, Regulated Rewriting in Formal Language Theory. Akademie-Verlag, Berlin and Springer-Verlag, Berlin (1989). | MR 1067543 | Zbl 0697.68067
[5] and, Petri nets algorithms in the theory of matrix grammars. Acta Inform. 31 (1994) 719-728. | Zbl 0834.68064
[6] , The Mathematical Theory of Context-Free Languages. McGraw Hill Book Comp., New York (1966). | MR 211815 | Zbl 0184.28401
[7] , Restricted one-counter machines with undecidable universe problems. Math. Syst. Theory 13 (1979) 181-186. | Zbl 0428.03038
[8] , On a conjecture about slender context-free languages. Theor. Comput. Sci. 132 (1994) 427-434. | Zbl 0938.68707
[9] , On lengths of words in context-free languages. Theor. Comput. Sci. 242 (2000) 327-359. | Zbl 0944.68099
[10] , The growth function of context-free languages. Theor. Comput. Sci. 255 (2001) 601-605. | Zbl 0973.68117
[11] , and, Characterization of the structure-generating functions of regular sets and the D0L systems. Inform. Control 36 (1978) 85-101. | Zbl 0378.68042
[12] and, The structure generating function of some families of languages. Inform. Control 32 (1976) 85-92. | Zbl 0338.68054
[13] , and, -bounded and semidiscrete languages. Inform. Control 51 (1981) 147-187. | Zbl 0507.68053
[14] and, Semidiscrete context-free languages. Internat. J. Comput. Math. 14 (1983) 3-18. | Zbl 0514.68072
[15] and, Thin and slender languages. Discrete Appl. Math. 61 (1995) 257-270. | Zbl 0831.68057
[16] , Length considerations in context-free languages. Theor. Comput. Sci. 183 (1997) 21-32. | Zbl 0911.68097
[17] and, Automata-Theoretic Aspects of Formal Power Series. Springer-Verlag (1978). | MR 483721 | Zbl 0377.68039
[18] , Slender matrix languages, in Developments in Language Theory, edited by G. Rozenberg, W. Thomas. World Scientific, Singapore (2000) 375-385. | Zbl 0996.68097