Charles Explorer logo
🇨🇿

On Pumping RP-automata Controlled by Complete LRG(\cent,$)-grammars

Publikace na Matematicko-fyzikální fakulta |
2022

Tento text není v aktuálním jazyce dostupný. Zobrazuje se verze "en".Abstrakt

We introduce complete LR(0)-grammars with sentinels (called complete LR(c,$)-grammars) to prepare tools for the study of pumping restarting automata controlled by this type of grammars. A complete LR(c,$)-grammar generates both a language and the complement of the language with sentinels.

Based on a complete LR(c,$)-grammar, we can construct a deterministic pumping restarting automaton performing pumping analysis by reduction on each word over its input alphabet. A pumping reduction analysis is a method where an input word is stepwise simplified by removing at most two continuous parts of the current word in a way that preserves (in)correctness of the word.

Each such simplification corresponds to removing parts of the current word that could be "pumped" in the sense of a pumping lemma for context-free languages. The computation of a pumping restarting automaton ends when the original word is shortened under a given length, and then it is decided about the correctness or incorrectness of the original input word.

This means that pumping restarting automata can analyze both correct and incorrect inputs with respect to a deterministic context-free language (DCFL). That gives an excellent formal basis for the error localization and the error recovery of DCFL.