A hierarchy of deterministic languages

摘要

An infinite hierarchy of deterministic context free languages is introduced. The hierarchy is defined by the number of accepting configurations required by deterministic pushdown automata recognizing the languages. The hierarchy is related to some well-known language families. As a consequence we get “relative closure” results for certain subfamilies of the deterministic languages.