Programming Research Group Research Report RR-04-23

K. Aehlig, J. G. de Miranda,C.-H. L. Ong

October 2004, 43pp.

Abstract

Recent work by Knapik, Niwinski and Urzczyn [KNU02] has revived interest in the connexions between higher-order grammars and higher-order pushdown automata. Both devices can be viewed as definitions for term trees as well as string languages. In the latter setting we recall the extensive study by Damm [Dam82], and Damm and Goerdt [DG86]. There it was shown that the language of a level-n higher-order grammar is accepted by a level-n higher-order pushdown automaton subject to the restriction of derived types, more recent rebranded as safety. We show that at level 2, if a string language is generated by an unsafe grammar, there is a (level-2, non-deterministic) safe grammar that generates the same language. Thus safety is not a restriction for level-2 string languages.