Context-free languages over infinite alphabets
type: Item
instance of: scholarly article
title: Context-free languages over infinite alphabets
zbMATH Open document ID: 0896.68088
author: Edward Y. C. Cheng
author: Michael Kaminski
published in: Acta Informatica
publication date: 1998-05-24T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 1154557
zbMATH Keywords: contextfree grammars
zbMATH Keywords: pushdown automata over infinite alphabets
MaRDI profile type: Publication
full work available at URL: s002360050120
OpenAlex ID: W1994458424
DOI: 10.1007/S002360050120
Recommended article: Classes of regular and context-free languages over countably infinite alphabets
Recommended article: Q4779173
Recommended article: Context-free complexity of finite languages
Recommended article: Automata over Infinite Alphabets
Recommended article: Fixed-point characterization of context-free ∞-languages
Recommended article: Q4874652
Recommended article: Q3774982
Recommended article: Q3685228
Recommended article: Q5526125
description: scientific article; zbMATH DE number 1154557