Complete characterization of context-sensitive languages
Miroslav Novotný (1974)
Kybernetika
Similarity:
Displaying similar documents to “Algebra grammars”
Complete characterization of context-sensitive languages
Comments on effective and unambiguous context-free languages
Eduard Kostolanský (1969)
Kybernetika
Similarity:
Two theorems about Galiukschov semicontextual languages
Gheorghe Păun (1985)
Kybernetika
Similarity:
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 -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...