An iteration theorem for simple precedence languages. (English) Zbl 0628.68060

An iteration theorem for simple precedence languages is presented. The theorem is then used to prove very easily that certain languages are not simple precedence. In addition, a strong characterization of simple precedence language is established. This is obtained by analyzing a nontrivial family of languages that includes typical languages which are not simple precedence languages and some similar languages which are in fact simple precedence. The iteration theorem is then generalized to deal with certain families of extended precedence languages. Using this theorem, it is shown that none of the languages proved to be nonsimple precedence is uniquely invertible (1,k) precedence for any \(k\geq 1\).


68Q45 Formal languages and automata
68N20 Theory of compilers and interpreters
Full Text: DOI