Classes of regular and context-free languages over countably infinite alphabets (Q1068559): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 01:12, 31 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Classes of regular and context-free languages over countably infinite alphabets |
scientific article |
Statements
Classes of regular and context-free languages over countably infinite alphabets (English)
0 references
1985
0 references
For a countably infinite alphabet \(\Delta\), the classes Reg(\(\Delta)\) of regular languages and CFL(\(\Delta)\) of context-free languages over \(\Delta\) are defined by way of an encoding. All the languages contained in these classes are decidable, and these classes do have many properties in common with the class of regular languages Reg(\(\Sigma)\) and the class of context-free languages CFL(\(\Sigma)\), respectively, where \(\Sigma\) is a finite alphabet. In particular, each of these classes can be characterized in a semantical way by a certain type of automata over \(\Delta\). Finally, the classes Reg(\(\Delta)\) and CFL(\(\Delta)\) are compared to the classes of languages over \(\Delta\) that are defined by Autebert, Beauquier, and Boasson.
0 references
regular languages
0 references
context-free languages
0 references