Journal:Informatica
Volume 10, Issue 1 (1999): Special Issue on Programming Theory, Information System Engineering, Software Engineering, and Artificial Intelligence, pp. 27–44
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.