Classes of regular and context-free languages over countably infinite alphabets (Q1068559)

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.