Informatica

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.