Abstrakt
We introduce context-free grammar with sentinels, CF(c|,$)-grammar, as a generalization of recently introduced LR(c|,$)- grammar. Original LR(c|,$)-grammars can be used to construct deterministic pumping restarting automata performing correctness and error preserving pumping analysis by reduction on each word over its input alphabet. Pumping analysis by reduction involves step-wise simplification of an input word by removing at most two continuous parts of the current word while preserving the correctness or incorrectness of the word. Each such simplification step corresponds to removing portions of the current word that can be "pumped" according to the pumping lemma for context-free languages, and thus, it does not use any nonterminals.
One-side pumping grammars are CF(c|,$)-grammars that allow removing just one continuous part in each step of pumping reduction. A complete CF(c|,$)-grammar generates both a language and its complement with sentinels. We show that complete one-side pumping CF(c|,$)-grammars characterize the class of regular languages, while LR(c|,$)-grammars that allow two-side pumping reductions characterize the class of deterministic context-free languages. LR(c|,$)-grammars that do not allow any one-side pumping reduction generate non-regular languages only.