FINITE-TURN PUSHDOWN AUTOMATA.

reportActive / Technical Report | Accession Number: AD0628204 | Need Help?

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

Author(s):
Ginsburg, Seymour ; Spanier, Edwin H.
Author Organization(s):
SYSTEM DEVELOPMENT CORP SANTA MONICA CALIF
Descriptive Note:
Scientific rept.,
Supplementary Note:
Prepared in cooperation with California Univ., Berkeley.
Annotation:
Finite-turn pushdown automata.
Pagination:
0044

Security Markings

DOCUMENT & CONTEXTUAL SUMMARY

Distribution:
Approved For Public Release

RECORD

Collection: TR
Identifying Numbers
Report Number(s):
Scientific-5, SDC-TM-738/020/00
Contract/Grant Number(s):
AF 19(628)-5166
Task Number(s):
563205
Project Number(s):
AF-5632
Monitor Series:
65-903
 Subject Terms
Communities of Interest:
No COI(s) Identified
Descriptor(s):
*MEMORY DEVICES, *COMPUTER PROGRAMMING, CONTEXT FREE GRAMMARS, AUTOMATA, COMPILERS
Field(s)/Group(s):
Linguistics, Computer Programming and Software, Computer Hardware
Keyword(s):
PUSHDOWN STORAGE
Report Date:
1965 Nov 01