Properties of syntax directed translations

摘要

Translations that can be expressed as generalizations of context free grammars and pushdown automata are defined. The types of translations defined are ordered according to power. For each type, certain necessary conditions that a translation be of that type are given. It is shown that T is a simple syntax directed translation if and only if there is a context free language L and homomorphisms h1 and h2 such that T={(h1(w), h2(w))‖w is in L}. Every syntax directed translation with one input symbol and one output symbol can be defined by a sequential transducer. For every syntax directed translation T, there is a constant c, such that for all w≠ε in the domain of T, there exists (w, x) in T, with |x|≤c|w|. A context free language is unambiguous if and only if it is the domain of a translation defined by a deterministic pushdown recognizer (pushdown automation with two input tapes).