COOPERATION IN CONTEXT-FREE GRAMMARS

A new dynamical measure of the descriptional complexity for context-fr ee grammars and languages, namely the degree of cooperation, is introd uced and studied. This measure is connected with respect to both famil ies of languages considered, namely the regular and context-free langu ages. We prove that the degree of cooperation is computable fbr regula r and unambigous context-free grammars and it is not computable for ar bitrary context-free grammars. The computability status of this measur e for languages remains to be investigated.