A GENERALIZATION OF CONTEXT FREE DETERMINISM,

Abstract

Nondeterministic Turing machines, under the restriction that each square be written on only a fixed number of times, recognize all and only context free languages. The deterministic subclass gives rise to a hierarchical extension of the pushdown deterministic languages. Unambiguity in terms of the machines is the same as grammatical unambiguity. (Author)

Document Details

Document Type
Technical Report
Publication Date
Nov 21, 1966
Accession Number
AD0651063

Entities

People

  • Thomas N. Hibbard

Organizations

  • System Development Corporation

Tags

DTIC Thesaurus Topics

  • Automata
  • Language

Readers

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