Electronic Resource
Springer
Acta informatica
35 (1998), S. 245-267
ISSN:
1432-0525
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract. In this paper we introduce context-free grammars and pushdown automata over infinite alphabets. It is shown that a language is generated by a context-free 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 context-free languages: decidability, closure properties, etc.. This provides a substantial evidence for considering context-free grammars and pushdown automata over infinite alphabets as a natural extension of the classical ones.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/s002360050120
Permalink
|
Location |
Call Number |
Expected |
Availability |
