WRITING PUSHDOWN ACCEPTORS,

Abstract

The paper introduces a new automaton, called a writing pushdown acceptor (abbreviated wpda), and investigates some of its properties. A wpda is essentially a two-way pushdown acceptor that can write on its input tape. A number of results about wpda are established. In particular, it is shown that (1) Each set accepted by a wpda is accepted by some wpda that halts for all inputs; (2) the family of sets accepted by deterministic wpda forms a Boolean algebra of sets, contains the family of context sensitive languages, and properly contains the family of sets accepted by deterministic two-way pushdown acceptors; and (3) the family of sets accepted by (deterministic) wpda is contained in the family of sets accepted by (deterministic) stack acceptors. In the deterministic case, the containment is shown to be proper. (Author)

Document Details

Document Type
Technical Report
Publication Date
May 14, 1968
Accession Number
AD0680783

Entities

People

  • George Mager

Organizations

  • System Development Corporation

Tags

DTIC Thesaurus Topics

  • Automata
  • Boolean Algebra
  • Language
  • Logic
  • Machines

Readers

  • Computational Modeling and Simulation
  • Computer Engineering
  • Marine Propulsion Engineering and Naval Architecture