FINITE-TURN PUSHDOWN AUTOMATA.

Abstract

A finite-turn pda is a pda in which the length of the pushdown tape alternatively increases and decreases at most a fixed bounded number of times during any sweep of the automation. This paper is a study of these finite-turn pda and the context free languages they recognize. These context free languages are characterized both in terms of grammars (two ways) and in terms of generation from finite sets by three operations. A decision procedure is given for determining if an arbitrary pda is a finite-turn pda. There is no decision procedure for determining if an arbitrary context free language is accepted by some finite-turn pda. (Author)

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1965
Accession Number
AD0628204

Entities

People

  • Edwin H. Spanier
  • Seymour Ginsburg

Organizations

  • System Development Corporation

Tags

DTIC Thesaurus Topics

  • Automata
  • Automation
  • California
  • Cooperation
  • Demographic Cohorts
  • Grammars
  • Language
  • Linguistics
  • Social Sciences

Readers

  • Geodesy
  • Mathematical Modeling and Probability Theory.
  • Speech Processing/Speech Recognition.