Context-free languages over infinite alphabets |
| |
| Authors: | Edward YC Cheng Michael Kaminski |
| |
| Affiliation: | (1) Department of Computer and Information Sciences and Engineering, University of Florida, Gainesville, FL 32611-2024, USA (e-mail: yccheng@cise.ufl.edu) , US;(2) Department of Computer Science, Technion – Israel Institute of Technology, Haifa 32000, Israel (e-mail: kaminski@as.technion.ac.il) , IL |
| |
| 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.
Received November 27, 1995 / March 4, 1997 |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
