Deterministic context free languages

Abstract

A number of results about deterministic languages (languages accepted by pushdown automata with no choice of moves) are established. In particular, (1) each deterministic language is unambiguous. (2) the complement of each deterministic language is a deterministic language. (3) numerous operations which preserve deterministic languages (for example, intersection with a regular set) are obtained. (4) several problems are shown to be recursively unsolvable.