DETERMINISTIC CONTEXT FREE LANGUAGES,

Abstract

A number of results about deterministic languages (languages accepted by pushdown automata with no choice of moves) are established. In particular, (1) each deterministic language is unambiguous. (2) the complement of each deterministic language is a deterministic language. (3) numerous operations which preserve deterministic languages (for example, intersection with a regular set) are obtained. (4) several problems are shown to be recursively unsolvable. (Author)

Document Details

Document Type
Technical Report
Publication Date
May 07, 1965
Accession Number
AD0624938

Entities

People

  • Seymour Ginsburg
  • Sheila Greibach

Organizations

  • System Development Corporation

Tags

DTIC Thesaurus Topics

  • Automata
  • Behavior And Behavior Mechanisms
  • Behavioral Disciplines And Activities
  • Behavioral Sciences
  • Cooperation
  • Group Dynamics
  • Language

Fields of Study

  • Computer science

Readers

  • Mathematical Modeling and Probability Theory.
  • Software Engineering.