Context-free languages over infinite alphabets
The paper deals with contextfree grammars and pushdown automata over infinite alphabets. It is shown that a language is generated by a contextfree grammar over an infinite alphabet if and only if it is accepted by a pushdown automaton over an infinite alphabet. Also, the generated (accepted) languages possess many of the properties of the ordinary contextfree languages: decidability, closure properties, etc.. This provides a substantial evidence for considering contextfree grammars and pushdown automata over infinite alphabets as a natural extension of the classical ones.
pushdown automata over infinite alphabets
scientific article; zbMATH DE number 1154557