Displaying similar documents to “On a class of languages”

On differentiation functions, structure functions, and related languages of context-free grammars

Jürgen Dassow, Victor Mitrana, Gheorghe Păun, Ralf Stiebe (2004)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

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 k -narrow) iff its differentiation function is bounded by a constant (by k ). 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...