A Generalization of Regular Expressions

Issue title: Programming Theory, Information System Engineering, Software Engineering, and Artificial Intelligence

Article type: Research Article

Authors: Gomozov, Aleksei L. | Stanevichene, Larisa I.

Affiliations: Department of Computational Mathematics and Cybernetics, Moscow State University, Moscow, Russia

Abstract: CF-expressions are defined which generalize the regular one. It is established that so called pseudo-coiterating CF-expressions characterize the regular sets. The results are used to develop some more characterizations of the regular sets: the pseudo-coiterating D-graphs and the pseudo-coiterating pushdown automata (PDAs). An algorithm is presented for deciding whether a device of three mentioned types is pseudo-coiterating or not. Apparently, the pseudo-coiterating PDAs form the most large of classes of PDAs the solvability of the question of belonging to which was proved and which are known as characterizations of the regular sets.

Keywords: D-graphs, regular expression generalization, characterization of context-free languages, pushdown automata, characterization of regular sets

DOI: 10.3233/INF-1999-10103

Journal: Informatica, vol. 10, no. 1, pp. 27-44, 1999