A hierarchy of real-time deterministic languages and their equivalence

摘要

An infinite hierarchy of real-time deterministic context free languages is introduced. It specializes the hierarchy of all deterministic languages based on the number of accepting configurations in deterministic pushdown automata accepting the languages. The recently found decision procedure for the equivalence of a real-time strict deterministic language and a deterministic language is then used to show that equivalence of two deterministic languages, one of which is real-time of finite rank in the hierarchy, is also decidable. It was recently shown how to decide whether a deterministic language is real-time strict. This result is used to obtain a decision procedure for a deterministic language checking whether it is real-time of finite rank, and computing its rank if it is finite.