STACK AUTOMATA AND COMPILING.

Abstract

Compilation consists of two parts, recognition and translation. A mathematical model is presented which embodies the salient features of many modern compiling techniques. The model, called the stack automaton, has the desirable feature of being deterministic in nature. This deterministic device is generalized to a nondeterministic device (nondeterministic stack automaton) and particular instances of this more general device noted. Sets accepted by nondeterministic stack automata are recursive. Each set accepted by a deterministic linear bounded automaton is accepted by some nonerasing stack automaton. Each context sensitive language is accepted by some (deterministic) stack automaton. (Author)

Document Details

Document Type
Technical Report
Publication Date
Nov 17, 1965
Accession Number
AD0628205

Entities

People

  • Michael A. Harrison
  • Seymour Ginsburg
  • Sheila A. Greibach

Organizations

  • System Development Corporation

Tags

DTIC Thesaurus Topics

  • Automata
  • Language
  • Mathematical Models
  • Models
  • Recognition

Readers

  • Computer Science/Computer Engineering/Data Science/Digital Signal Processing.
  • Mathematical Modeling and Probability Theory.