Tree-oriented proofs of some theorems on context-free and indexed languages

Abstract

In this paper we study some applications and generalizations of the yield theorem: the yield of a recognizable set of trees (dendrolanguage) is an indexed language [1]. Standard results on context-free languages can be obtained quickly using this theorem. We consider here the Peters-Ritchie theorem [4]: the language analyzable by a finite set of CS rules is CF.