Context-free languages over infinite alphabets (Q1386414)

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.