Classes of regular and context-free languages over countably infinite alphabets |
| |
Authors: | Friedrich Otto |
| |
Affiliation: | Fachbereich Informatik, Universität Kaiserslautern, Postfach 3049, 6750 Kaiserslautern, West Germany |
| |
Abstract: | For a countably infinite alphabet Δ, the classes Reg(Δ) of regular languages and CFL(Δ) of context-free languages over Δ 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(Σ) and the class of context-free languages CFL(Σ), respectively, where Σ is a finite alphabet. In particular, each of these classes can be characterized in a semantical way by a certain type of automata over Δ. Finally, the classes Reg(Δ) and CFL (Δ) are compared to the classes of languages over Δ that are defined by Autebert, Beauquier, and Boasson. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|