Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-15T14:40:12.767Z Has data issue: false hasContentIssue false

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

Published online by Cambridge University Press:  15 June 2004

Jürgen Dassow
Affiliation:
Otto-von-Guericke-Universität Magdeburg, Fakultät für Informatik, PSF 4120, 39016 Magdeburg, Germany; dassow@iws.cs.uni-magdeburg.de.; stiebe@iws.cs.uni-magdeburg.de.
Victor Mitrana
Affiliation:
University of Bucharest, Institute of Mathematics, Str. Academiei 14, 70109 Bucuresti, Romania.Rovira i Virgili University, Research Group in Mathematical Linguistics, Pça. Imperial Tarraco 1, 43005, Tarragona, Spain; vmi@fll.urv.es.
Gheorghe Păun
Affiliation:
Institute of Mathematics of the Romanian Academy, PO Box 1–764, 70700 Bucuresti, Romania; George.Paun@imar.ro.
Ralf Stiebe
Affiliation:
Otto-von-Guericke-Universität Magdeburg, Fakultät für Informatik, PSF 4120, 39016 Magdeburg, Germany; dassow@iws.cs.uni-magdeburg.de.; stiebe@iws.cs.uni-magdeburg.de.
Get access

Abstract

We introduce the notion of a differentiation function of acontext-free grammar which gives the number of terminal words that can bederived in a certain number of steps. A grammar is called narrow (ork-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 languagesand narrow grammars to slender languages. We discuss the decidability of the equivalence of grammars with respect to the differentiation function andstructure function and prove the decidability of the k-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.

Information

Type
Research Article
Copyright
© EDP Sciences, 2004

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable