Accession Number:

AD0628204

Title:

FINITE-TURN PUSHDOWN AUTOMATA.

Descriptive Note:

Scientific rept.,

Corporate Author:

SYSTEM DEVELOPMENT CORP SANTA MONICA CALIF

Personal Author(s):

Report Date:

1965-11-01

Pagination or Media Count:

44.0

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

Subject Categories:

  • Linguistics
  • Computer Programming and Software
  • Computer Hardware

Distribution Statement:

APPROVED FOR PUBLIC RELEASE