Context-free languages over infinite alphabets (Q1386414)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Context-free languages over infinite alphabets |
scientific article; zbMATH DE number 1154557
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Context-free languages over infinite alphabets |
scientific article; zbMATH DE number 1154557 |
Statements
Context-free languages over infinite alphabets (English)
0 references
24 May 1998
0 references
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.
0 references
contextfree grammars
0 references
pushdown automata over infinite alphabets
0 references
0.9354899
0 references
0.89391404
0 references
0 references
0.8920225
0 references
