Formal Languages with Oracles

Candidate: Weixelbaum,Elia S.

Abstract

A relativization of formal language theory is studied in this dissertation. Specifically, we examine possible relativizations of the four language classes of the Chomsky hierarchy. Definitions are given for oracle finite automata, oracle pushdown automata, oracle linear bounded automata, and oracle Turing machines. The relativized regular languages are characterized via results derived from AFL (abstract families of languages) theory. We then use this characterization to help us derive a relativization of the Chomsky-Schutzenberger theorem for relativized context free languages. We examine relativized recursively enumerable (r.e.) languages by studying oracle Turing machines and also by suggesting a definition for an oracle phrase structure grammar. We demonstrate two different types of equivalences between these two models. The context sensitive languages are relativized in the same manner as are the r.e. languages, although there are difficulties in proving the respective results for the context sensitive case. Several unresolved questions remain in this case.