Intercalation theorems for stack languages

Abstract

This paper develops necessary conditions for languages to be stack generable, stack decidable, and non-erasing stack generable. The result for stack generable languages shows that the languages {an3¦n≥ 0} and {an bn2 cn ¦n≥0) are not stack generable. It also shows that the language {am bm2 cn ¦m, n&ge1} υ{am bn2 cn ¦m, n≥1} is inherently ambiguous as a stack language. In addition, it shows that the infiniteness problem for stack generable languages is solvable.