We introduce complete LR(0)-grammars with sentinels (called complete LR(¢,$)-grammars) to prepare tools for the study of pumping restarting automata controlled by this type of grammars. A complete LR(¢,$)-grammar generates both a language and the complement of the language with sentinels. Based on a complete LR(¢,$)-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.
accepted. Each reduction must be error preserving, i.e., no word outside the target language can be rewritten into a
pers [
Some linguistic and non-linguistic motivations for this has several additional properties. In each step of pumping
paper can be found already in [
Reduction analysis is a method for checking the cor- Informally, a complete grammar (with sentinels ¢ and rectness of an input word by stepwise rewriting some $) is an extended context-free grammar that has two part of the current form with a shorter one until we obtain initial nonterminals and . Such grammar has a a simple word for which we can decide its correctness ifnite alphabet Σ of terminals not containing ¢ and $, easily. In general, reduction analysis is nondeterministic, finite alphabet of nonterminals and a set of rewriting and in one step, we can rewrite a substring of a length rules of the form → , where is a nonterminal and limited by a constant with a shorter string. An input is a string of terminals, nonterminals and sentinels ¢, word is accepted if there is a sequence of reductions such $. The language generated by the grammar is the set that the final simple word is from the language. Then, of words such that the word {¢} · · { $} can be intermediate words obtained during the analysis are also derived from the initial nonterminal and the set of ITAT’22: Information technologies – Applications and Theory, Septem- words derived from the second initial nonterminal is ber 23–27, 2022, Zuberec, Slovakia exactly {¢} · (Σ * ∖ ) · { $}. $ martin.platek@mf.cuni.cz (M. Plátek); Pumping reduction analysis corresponds to a complete frantisek.mraz@mf.cuni.cz (F. Mráz); grammar when for each pair of terminal words , (pDa.rdPurbůsškaa)@dcs.fmph.uniba.sk (D. Pardubská); prusa@fel.cvut.cz such that can be reduced to , it holds that there 0000-0003-3147-6442 (M. Plátek); 0000-0001-9869-3340 (F. Mráz); are some terminal words 1, 2, 3, 4, 5, and a nonter0000-0001-9383-8117 (D. Pardubská); 0000-0003-4866-5709 minal such that = 12345, = 135, and (D. Průša) ⇒* 15 ⇒* 1245 ⇒* 12345, © 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License where equals or . Additionally, there exists a
constant that depends only on the grammar such rest of the tape if the tape contents is shorter than ). that each word of length at least can be reduced to a The computation of is controlled by the transition shorter word. function
The main result of the paper is that for each determin- : ( ∖ (A ∪ R)) × () → istic context-free language, there exists a complete gram- ( × { MVR, PREPARE }) ∪ mar and a deterministic restarting RP-automaton ((A ∪ R) × { HALT }) ∪ that performs pumping reduction analysis on any input {RESTART () | ∈ ≤ (− 1)}. word . The last phase of the computation of on will produce a terminal word ′ that is not longer than Here () denotes the powerset of the set , () the constant . If ¢′$ is generated from according is the set of possible contents of the read/write window to , then ′ (and thus also ) is accepted by . Oth- of , where for , ≥ 0 tehrwenise,′ i(fa¢nd′t$h uiss gaelsnoera)teisdrferjoemctedbyacco.rding to , () = ({¢} · Σ − 1) ∪ Σ ∪ (({Σ¢≤ }·− Σ 1 ≤ · {− $2} )·{∪$}),
The paper is structured as follows. Section 2 introduces Σ ≤ = ⋃︀ Σ and ≤ (− 1) = ⋃−︀1 (). RP-automata and LR(0)-grammars, and presents their ba- =0 =0 sic properties. LR(0)-grammars are used for constructing The transition function represents a finite set of a complete grammar for any deterministic context-free four diferent types of instructions (transition steps). Let language. , ′, be states from , ∈ (), ∈ ≤ (),
Section 3 introduces complete grammars and presents ∈ ≤ (− 1) and be in state with being the a method for constructing a complete grammar for any contents of its read/write window: given deterministic context-free language. (1) A move-right instruction of the form (, ) →
Section 4 presents the main results of this paper. Here, (′, MVR) is applicable if ∈/ Σ * $. It causes to enter we show that for any complete grammar constructed the state ′ and to move its read/write head one item to in Section 3, we can construct a deterministic restarting the right.
RP-automaton that performs pumping reduction analysis (2) A preparing instruction of the form (, ) → according to for any input word. ( , PREPARE ) changes ’s state to a restarting state
Finally, Section 5 summarizes the results of the paper that determines the next instruction, which must be a and gives an outlook for future research. restarting instruction.
(3) A restarting instruction is of the form ( , ) →
2. Basic notions sentinel, contains the corresponding sentinels, too. This
instruction is applicable if is a prefix of the contents
At first, we introduce our base automata model called of the read/write window. When executed, replaces
RP-automata. RP-automata are restarting automata [
An RP-restarting automaton, or an RP-automaton, dow contains ¢. Note that the state unambiguously = (, Σ , ¢, $, 0, , , A, R) (with -bounded gives the pair (, ). We can assume that all pairs (, ) lookahead) is a device with a finite state control unit where || > || and the word can be replaced with with the finite set of states containing two disjunctive by some RESTART instruction are ordered and that subsets A, R of accepting and rejecting states, respec- is the index of (, ) in that sequence. Thus, although tively. The automaton is equipped with a head moving the RP-automaton is generally nondeterministic, each on a finite linear flexible tape of items (cells). The first RESTART instruction of corresponds unambiguitem of the tape always contains the left sentinel sym- ously to one restart state . boothl e¢r, tihteemlacsotnotnaeintshea rsiygmhtbsoelnftrionmel sayfinmitbeolal$p,haanbdeteacΣ h (′(,4H) AALTha)l,twinhgerinestr′u∈ctionA oofr th′e∈formR, fin(is,he)s th→e (not containing ¢, $). The head has a flexible read/write computation and causes to accept or reject, respecwindow of length at most (for some ≥ 1) – scans tively, the input word. consecutive items or the rest of the tape when the dis- Thus, the set of states can be divided into three groups – tance to the right sentinel $ is less than . We say that the halting states A ∪ R, the restarting states (involved is of window size . In the initial configuration on an on the left-hand side of restarting instructions), and the input word ∈ Σ * , the tape contains the input word rest, called the transition states. delimited by the sentinels ¢ and $, the control unit is in A configuration of an RP-automaton is a word the initial state 0, and the window scans the left sentinel , where ∈ , and either = , where denotes ¢ and the first − 1 symbols of the input word (or the the empty word, and ∈ {¢} · Σ * · { $} or ∈ {¢} · Σ * and ∈ Σ * · { $}; here represents the current item scanned by a restarting instruction in a cycle is not state, is the current contents of the tape, and it is increasing during the whole computation. It means that understood that the read/write window contains the first during any computation of a monotone RP-automaton symbols of or all symbols of if | | < . An initial the rightmost scanned items by restarting operations do (restarting) configuration is 0¢$, where ∈ Σ * . A not increase their distances from the right sentinel $. rewriting configuration is of the form , where is Considering a deterministic RP-automaton a restarting state. = (, Σ , ¢, $, 0, , , A, R), it is for us conve
A computation of is a sequence = 0, 1, . . . , nient to suppose it to be in the strong cyclic form; it of configurations of , where 0 is a restarting con- means that the words of length less than , being the ifguration, ℓ+1 is obtained from ℓ by a step of , for length of its read/write window, are immediately (hence all ℓ, 0 ≤ ℓ < , denoted as ℓ ⊢ ℓ+1, and ⊢* is the in a tail) accepted or rejected, and that performs at reflexive and transitive closure of the single-step relation least one cycle (at least one restarting) on any longer ⊢ . word. For each RP-automaton , we can construct an
In general, an RP-automaton can be nondeterministic, RP-automaton ′ in strong cyclic form accepting the
i.e. there can be two or more instructions with the same same language as but possibly with greater size of
left-hand side. If that is not the case, the automaton the read/write window [
An input word w is accepted by if there is a com- det- denotes the deterministic version, similarly monputation that starts in the initial configuration with the monotone version. Prefix scf- denotes the version (bounded by sentinels ¢, $) on the tape and finishes in in the strong cyclic form. ℒ(), where is some class an accepting configuration where the control unit is in of automata, denotes the class of languages accepted by one of the accepting states. ( ) denotes the language automata from . E.g., the class of languages accepted consisting of all words accepted by ; we say that by deterministic monotone RP-automata is denoted by accepts the language ( ). ℒ(det-mon-RP).
Let be deterministic. ( ) denotes the language Since all computations of RP-automata are nfiite and consisting of all words rejected by ; we say that the correctness preserving property holds for all deterrejects the language ( ). ministic RP-automata, the following proposition is obvi
Restarting steps divide any computation of an RP- ous. automaton into certain phases that all start in the initial state in restarting configurations with the read/write Proposition 2. The classes ℒ(det-mon-RP) and window in the leftmost position. In a phase called cycle, ℒ(det-RP) are closed under complement. the head moves to the right along the input list (with its Definition 3. Let = (, Σ , ¢, $, 0, , , A, R) be read/write window) until a restart occurs – in that case, a det-RP-automaton and ∈ Σ * . the computation is resumed in the initial configuration on Let AR(, ) = (, 1, 2, · · · , ), where ⇒ the new, shorter word. The phase from the last restart to 1 ⇒ 2 ⇒ · · · ⇒ , and cannot be reduced the halting configuration is called tail. This immediately by . We say that AR(, ) is the analysis by reduction implies that any computation of any RP-automaton is of by . ifnitTeh(eenndeixntgpirnoapohsailttiionngesxtaptree)s.ses a certain lucidness of ARL(etA)Ris(ana)ly=sis{bAy Rre(duc,tio)n|by∈Σ . * }. We say that computations of deterministic RP-automata. The no- Let AR(A, ) = {AR(, )| ∈ ( )}. We say tation ⇒ means that there exists a cycle of that AR(A, ) is accepting analysis by reduction by . starting in the initial configuration with the word on Let AR(R, ) = {AR(, )| ∈ ( )}. We say its tape and finishing in the initial configuration with the that AR(R, ) is rejecting analysis by reduction by . word on its tape; the relation ⇒* is the reflexive and transitive closure of ⇒ . We say that reduces to 2.1. LR(0) grammars if ⇒ .
The validity of the following proposition is obvious.
The proof of our main result is strongly based on the
Proposition 1. (Correctness preserving property.) theory of LR(0) grammars. We will recall the definition
Let be a deterministic RP-automaton and ⇒* for and properties of LR(0) grammars from Harrison [
By a monotone RP-automaton, we mean an RP- is a set of nonterminals, Σ is a set of terminals, ∈ automaton where the following holds for all computa- is the initial symbol and is a finite set of rules of the tions: the number of items to the right from the rightmost form → , for ∈ and ∈ ( ∪ Σ) * . We use a common notation ⇒ for a right derivation rewriting stored at the bottom of the pushdown. Let ∈ Σ * denote step according to . For two words , ′ ∈ ( ∪ Σ) * , the unread part of the input, and , where ∈ * and ⇒ , if there exist words , ∈ ( ∪ Σ) * , ∈ Σ * ∈ , is the contents of the pushdown. Then, the parser and nonterminal ∈ such that = , = performs repeatedly the following actions: and → is a rule from . The reflexive and transitive closure of the relation ⇒ we denote as ⇒*.
Definition 4 ([
= ,
In general, the identification of a handle in a string is not uniquely defined, which is not true for LR(0) grammars.
Definition 5. Let = (, Σ , , ) be a reduced contextfree grammar such that ⇒+ is not possible in . We say is an (0) grammar if, for each , ′, ∈ Σ * , , , ′, , ′ ∈ ( ∪ Σ) * , and , ′ ∈ , (a) ⇒* ⇒ = (b) ⇒* ′′ ⇒ ′ ′ = ′ implies ( → , | |) = (′ → ′, | ′ ′|).
1. If ( ) = ℎ , then a) if = , then the parser outputs an
error and rejects the input word, b) if = ′, for some ∈ Σ and ′ ∈ Σ * , then i. if (, ) = , then the parser outputs an error and rejects the input word, ii. if (, ) ̸= , then the parser pushes and (, ) onto its pushdown. 2. If ( ) = , where is a rule → from , then pops 2| | symbols from the pushdown and outputs the rule . Let ′ be the table that is uncovered at the top of the pushdown.
a) If ′ = 0, = , and = , then the parser accepts. The output is the reversed sequence of rules that, starting from the initial nonterminal , when applied iteratively on the rightmost nonterminal in the current word from ( ∪ Σ) * , produces the input . b) If ( ′, ) = , then the parser out
puts an error and rejects the input word. c) Otherwise, pushes and ( ′, ) onto its pushdown.
Note that as a consequence of the above definition we have that = ′, = ′, = ′, = = ′ ′ and = ′. Thus, if is an LR(0) grammar, then the rightmost derivation of the word by and the left- In what follows, we will refer to an LR(0) analyzer as right analysis is unique (deterministic). In this paper, we a pushdown automaton. Based on the way how it is conconsider (0) grammars rather as analytical grammars. structed, the pushdown automaton has several properties A language generated by an LR(0) grammar is called an that are essential for our constructions below: LR(0) language.
In [
corresponds to a unique derivation tree. • Let at some step of the computation of on input the contents of its pushdown store be 0 1 1 2 · · · − 1 , for an integer ≥ 0, 0, 1, . . . , ∈ , 1, . . . , ∈ ( ∪ Σ) , = , where ∈ Σ * is the already processed prefix of and ∈ Σ * is the unread part of . : → {ℎ , } ∪ { | ∈ } is
the parsing action function, and : × ( ∪ Σ) → ∪ {} is the goto
function.
We will omit the details of how the set of tables and the functions and are constructed. But we will describe how the LR(0) parser for the LR(0) grammar works on an input word . At first, an initial table 0 is – If ( ) ̸= , then there exists a word
such that ⇒* 1 · · · ⇒* . – If ( ) = , then there is no word such that ⇒* 1 · · · ⇒* .
That is, for all words ∈ Σ * , ̸∈ (). – There exist words 1, 2, . . . , ∈ Σ * such that = 1 · · · and ⇒* , for = 1, . . . , . There exist derivation sub-trees 1, . . . , according to such that the root of is labeled and the labels of the leaves of concatenated is the word , for = 1, . . . , . 3. LR(¢,$)-grammars We introduce LR(¢,$)-grammars to obtain grammars that can control RP-automata in such a way that this type of automata will characterize DCFL and regular languages by pumping reductions.
Definition 6. Let ¢, $ ∈/ ( ∪ Σ) and = (, Σ ∪ {¢, $}, , ) be an LR(0) grammar generating a language of the form {¢} · · { $}, where ⊆ Σ * , and does not occur in the right-hand side of any rule from .
We say that is an LR(¢,$)-grammar. We denote the set of LR(¢,$)-grammars by LRG(¢, $). W.l.o.g., we suppose that an LR(¢,$)-grammar does not contain rewriting rules of the form → for any nonterminal ∈ .
We say that is the internal language of and denote it as (). 1
1 2 ⇒* ⇒* 12 ⇒* 12 (1)
is some (sub)class of grammars or automata, denotes the we say that 12 ⇐ () is a pumping reduction class of languages generated/accepted by grammars/au- according to grammar . Here ⇒ denotes the rewrittomata from . E.g., the class of languages generated ing relation according to a rule of that need not be a by linear LR(¢,$)-grammars is denoted by ℒ(-LR(¢,$)). right derivation. Then ⇒* is the reflexive and transitive Similarly, for some (sub)class of LR(¢,$)-grammars we closure of ⇒. take for internal languages ℒ() = { | {¢}· ·{ $} ∈ If a word can be generated by , then there exists a ℒ()}. sequence of words 1, . . . , from Σ * , for some integer
Based on the closure properties of DCFL shown, e.g., in ≥ 1, such that = 1, there are pumping reductions
[
Proposition 7. ℒ(LRG(¢, $)) = . Let be a derivation tree corresponding to
derivaProof. Let ⊂ Σ * , and be a DCFL. Let ¢ and $ be tion (1), where = 12. See Fig. 1. The proper
not from Σ . We know from [
On the other hand, if is the inner language of an get the derivation tree (2) for a longer word (2) =
LR(¢, $)-grammar, the language {¢} · · { $} is LR(0), 1222. If we replace 2 with 1 times, we obtain
and it can be accepted by a deterministic pushdown au- the derivation tree (+1) for the word ( + 1) =
tomaton. Using closure properties of DCFL [
Note. It is not hard to see that the languages from We say that = 12 is a pumping prefix by ℒ((¢, $)) are prefix-free and sufix-free languages with the pumping pattern (, 1, , , 2). We also say at the same time. that is an (, 1, , , 2)-pumping prefix. If |1| > 0 and |2| > 0, we say that is a two-sided pumping prefix. Otherwise, we say that is a one-sided pumping prefix by . maximal length of the right-hand side of the rules from . If is a non-pumping accepting tree according to then it cannot have more than terminal leaves. If has more than leaves, then there exists a path from a leaf to the root of containing at least + 1 nodes labelled by nonterminals, and is not a non-pumping tree. Let = . We say that is the grammar number of .
Note that any word from () of length greater than must contain a core pumping pattern by . On the other hand, the length of any non-pumping accepting word by is at most .
We can see the following obvious proposition that summarizes the leftmost pumping properties of LR(¢, $)grammars, which we will use in the following text. It is a direct consequence of the previous definitions and the properties of LR(0)-grammars and their LR(0) analyzers.
Proposition 9. Let = (, Σ ∪ {¢, $}, , ) be an LR(¢,$)-grammar generating (analyzing) the language {¢} · · { $}. Let be an e-leftmost pumping prefix by with the pumping pattern (, 1, , , 2), and 12 ⇐ (,) be the corresponding smallest eleftmost pumping reduction by . Then
We say that 1 is the pumping tree of . Let us recall that, for any ∈ Σ * , it holds that 12 ∈ () if ∈ ().
Definition 8. Let be a (, 1, , 2)-pumping prefix by , and , 1, , 2, , , 1 be as on Fig. 1. We say that is an e-leftmost (elementary leftmost) pumping prefix by , and that (, 1, , , 2) is an e-leftmost pumping pattern if there is no proper prefix of such that it has a pumping pattern diferent from (, 1, , , 2).
We say in this case that 1 is the e-leftmost pumping tree.
Let be a word from Σ * . We write 12 ⇐ (,) , and say that 12 ⇐ (,) is an e-leftmost pumping reduction by , and that (, 1, , , 2) is also the pumping pattern of the e-leftmost pumping reduction 12 ⇐ (,) . We also say that 12 ⇐ (,) is an e-leftmost (, 1, , , 2)pumping reduction by , and that 12 ⇐ (,) is the smallest e-leftmost (, 1, , , 2)-pumping reduction by .
Note that, in the above definition, the word 12 need not be generated by , but 12 ⇐ (,) is still an e-leftmost pumping reduction by . This is important, as we will use such reduction also when ana- (a) Any ∈ {¢} · · { $} determines its derivation lyzing words not generated by . tree by unambiguously.
The notion of e-leftmost pumping reduction gives us (b) An e-leftmost pumping prefix by determines its a basis for a special type of analysis by reduction for pumping tree unambiguously. (), and mainly for analysis by reduction for (). (c) 1+12+1 ⇐ (,) 12 is an eThe next notions are the most important notions of this leftmost pumping reduction by for any , ≥ paper. 0, and ∈ Σ * .
Core pumping pattern. We say that a pumping pattern (d) ¢$ ∈ () if ¢12$ ∈ () for any (, 1, , , 2) by is a core pumping pattern if there ≥ 0, and any ∈ Σ * . is such that cannot be reduced by any pumping (e) Let = 12 ⇐ (,) be an ereduction by . We say that the tuple (1, , , 2) is a leftmost pumping reduction by . Then is deterpumping core by . mined unambiguously by the e-leftmost pumping One-sided and two-sided (core) pumping pattern. prefix 12.
Let (, 1, , , 2) be a (core) pumping pattern by (f) ¢12$ ∈ () if ¢1+2+$ ∈ . We say that (, 1, , , 2) is a one-sided (core) pumping pattern if 1 = , or 2 = . We say that () for all , , ≥ 0. (, 1, , , 2) is a two-sided (core) pumping pattern if The previous proposition is essential for our further 1 ̸= , and 2 ̸= . considerations. It shows that, for a non-empty 1, the Non-pumping accepting trees/words/derivations. distance of the place of pumping from the left end is not Let ∈ Σ * and limited, and the position of pumping is determined by the pumping prefix of the pumping reduction. ⇒ 0 ⇒ 1 · · · ⇒ (2) Observation. It is not hard to see that for any e-leftmost pumping pattern = (, 1, , , 2) there exists a prefix 1 of such that = (1, 1, , , 2) is a core pumping pattern. We say that corresponds to . be a right derivation by . Let be the derivation tree corresponding to derivation (2). Let no repetition of a nonterminal occurs on any path from the root of to a leaf of . We say that is a non-pumping accepting tree, Example 1. Consider the non-regular deterministic derivation (2) is a non-pumping accepting derivation, and context-free language = {¢$ | ≥ 1} with the is a non-pumping accepting word by . internal language { | ≥ 1} that is generated by Notation. Let = (, Σ , , ) be an LR(¢,$)-grammar, the LR(¢,$) grammar = ({, 1, , }, {, }, , )), be the number of nonterminals of , and be the Item set parsing action function { → ¢ · 1$, 1 → · 1, 1 → · } {1 → · 1, 1 → · , 1 → · 1, 1 → · } ¢ ¢+ ¢+1 ¢1$ ¢+ ¢+1 ¢+1 shift shift shift shift shift reduce → ¢1$ reduce 1 → reduce 1 → 1 start 0 ¢ 1 1 3 2 $ 1 5 4 6 7 (0) automaton states and regular expressions representing words reaching the states from the initial state 0.
′, | ′ ′|), because = 1, = , = , = $, for any ≥ 0.
The pumping notions can be illustrated in Fig. 2 with a derivation tree for = ∈ (), where = ¢,
For = ¢, =
¢ is an e-leftmost (, , 1, , )-pumping prefix
by , and 1 is an eleftmost pumping tree of . The pumping pattern of by is (, , 1, , ) and ¢ ⇐ () ¢ is an e-leftmost (, , 1, , )-pumping reduction by . Realize that a pumping reduction by can be applied to any word ¢, where , > 1, including the cases when ̸= . .
Moreover, (, , 1, , ) is a core pumping pattern by
Table 1 lists the set of tables of the (0) automaton for the grammar together with the corresponding parsing action function . The column with regular expressions summarizes by which strings are the particular states reachable from the initial state.
Table 2 lists the corresponding goto function of the LR(0) analyzer.
The goto function of the LR(0) automaton can be represented as a finite automaton
with tables as states (see Fig. 3). Note that state 4 is accepting and states 5, 7 are reducing.
Let us interpret all reducing states of the LR(0) automaton as accepting states of the finite automaton
. What is the regular language accepted by automaton ? The language contains all prefixes (,
∈ ( ∪ Σ) * ) of right sentential forms according to (obtained from the initial nonterminal using right derivation rewriting steps) such that is a right-hand side of a production rule of and there is no proper prefix that can be reduced according to . Formally: () = { | , ∈ ( ∪ Σ) * , ∃ ∈ Σ * , ∈ : ⇒* ⇒ }
State 0 1 2 3 4 5 6 7 (, ¢)
1 error error error (, ) error 2 2 error error error (, ) error error error 5 7 (, $) error error error
4 error (, ) (, 1) error 3 6 error error Goto function of the LR(0) analyzer for grammar . Note that for reduction states 4, 5, and 7 the goto function is not defined. Similarly, the goto function is not defined for the initial nonterminal .
The automaton enables to distinguish two types of ∈ Σ * . The accepting and rejecting analytic trees are errors with respect to ().
¢* + ¢+1. 1) A correct non-empty prefix of () which is turned incorrect by appending the right sentinel. This corresponds to all strings
∈ (¢ · { , , }* ) such that, after reading a prefix of a sentential form, with undefined transition for the automaton reaches a state ∈ $. All such strings
{0, 1, 2, 6} are represented by the regular expression 1 = 2) A correct non-empty prefix of () which is turned incorrect by appending one more symbol tial forms with a prefix of the form from {, , 1}. This corresponds to all senten
¢ , where
∈ {, , 1}* and ∈ {, , 1}, such that, after reading ¢ , the automaton reaches a state ∈ {0, 1, 2, 3, 6} with an error transitions for .
These strings are represented by the regular expression 2 = ¢+¢1(++1)+¢+1(+1). expression
Now, the (¢, $)-grammar generating the language ¢ · () · $ can be obtained by transforming the regular
1$ + 2( + )* $ into an equivalent regular grammar followed by adding productions of the grammar . This is the essential observation for constructing complete LR(¢,$)-grammar below. 3.2. Complete LR(¢,$)-grammars In this section, we introduce the complete LR(¢, $)grammar that will be used for constructing scf-mon-RPautomaton performing (complete) pumping analysis by reduction on any word over its input alphabet Σ . A complete LR(¢, $)-grammar is a normalized grammar that analyzes both its internal language and its complement and which, in its analytic mode, returns exactly one derivation tree for each input word of the form ¢$, where distinguished by the nonterminal under their root.
One-sided LR(¢,$)-grammar.
Let be an LR(¢,$)grammar. We say is a one-sided grammar if all its core pumping patterns are one-sided infixes.
Definition 10.
An LR(¢,$) grammar = (, Σ , , ) is called a complete LR(¢,$) grammar if 1. () = {¢} · Σ * · { $}. 2. → | , where , ∈ , are the only rules in containing the initial nonterminal . No other rule of contains or in its righthand side. 3. The languages () and () generated by () = {¢} · Σ * · { $}. the grammars = (, Σ , , ) and = (, Σ , , ), respectively, are disjoint and complementary with respect to {¢} · Σ *
· { $}. That is, () ∩ () = ∅ and () = () ∪ We will denote the grammar as = (, ). Further, we will call and as accepting and rejecting grammar of the complete LR(¢,$)-grammar , respectively.
Now we will prove the main theorem.
Theorem 1. For any LR(¢,$)-grammar , there exists a complete LR(¢,$)-grammar = (, ).
Proof. Let = (, Σ
∪ {¢, $}, , ) be an LR(¢,$)-grammar. We will show how to construct a complete LR(¢,$)-grammar = (, ) = ( ∪ ∪ {}, Σ such that and are new nonterminals not contained
∪ {¢, $}, , ∪ ∪ { → , → }) in , is from the new set of nonterminals . The construction utilizes the fact that for each word from the complement of (), LR(0) analyzer of can detect the shortest prefix of such that each word of the form belongs to the complement of (), where , , ∈ ( ∪ Σ) * .
and 0 ∈ be the initial state (table) of the corresponding LR(0) automaton. Let = ∪ {}, where is for generating arbitrary sufixes of words from a new nonterminal not contained in ∪ . The set · · · ⇐ of rules will contain rules → |$, for all ∈ Σ , Based on the goto function of the LR(0) analyzer for , we add the following set of rules into Σ * · { $}. analysis by reduction of by and by as well.
(,) , and there is not any such that ⇐ (,) . We say that AR(, ) is a pumping by . by .
Let ∈ (). We take AR(, ) = AR(, ).
Let ∈ (). We take AR(, ) = AR(, ).
Let AR() = {AR(, ) | ∈ Σ * }. We say that AR() is pumping analysis by reduction by .
Let AR(A, ) = {AR(, )| ∈ ()}. We say that AR(A, ) is accepting pumping analysis by reduction
Let AR(R, ) = {AR(, )| ∈ ()}. We say that AR(R, ) is rejecting pumping analysis by reduction Observe that the complete grammar constructed ac- Theorem 1, we can construct an RP-automaton with the { { → $ | ∈ , (, $) = }.
→ | ∈ , ∈ Σ ∪ , (, ) = } ∪
Now it is easy to see that all words of the form ¢$, where ∈ Σ * , that are rejected by the LR(0) analyzer for can be generated from the nonterminal 0. Hence, we set = 0. Note that we did not include rules with the left sentinel ¢ into the set defined in (3), because the complete grammar should generate only words of the form ¢$, for ∈ Σ * .
Additionally, the grammar = ( ∪ ∪
∪ {¢, $}, , ∪ ∪ { → , → }) is an LR(¢,$)-grammar, as the corresponding LR(0) analyzer for can be obtained by modifying the LR(0) analyzer for .
(3) cording to the above construction has further interesting properties: 1. For each word of the form ¢$, where ∈ Σ * , there is exactly one derivation tree according to . Under the root of , there is a node labelled either by or . If it is , the word is generated by the accepting grammar . Otherwise, it is generated by the rejecting grammar . 2. Let be a derivation tree according to . If a node from is labelled by a nonterminal from , then all its descendant nodes are labelled only by symbols from . 3. Let be a derivation tree according to . If a node from is labeled by a nonterminal from , then all nodes on the path from to the root of (except the root itself) are labelled only by symbols from . 4. The new rules added in the above construction if is a one-sided LR(¢, $)-grammar, then and have only one-sided core pumping patterns.
enable only one-sided pumping patterns. Thus, input alphabet. More precisely, in the cycles of its comDefinition 11.
Let = (, Σ
∪ {¢, $}, , ) be a com(, 1, 2, . . . , ), where plete LR(¢,$)-grammar, and be its accepting and rejecting grammars. Let ∈ (), AR(, ) = ⇐ (,) 1
⇐ (,) 2 such that ⇐ (,) · · · ⇐
(,) , and there is not any ⇐ (,) . We say that AR(, ) is a pumping analysis (by reduction) of by and as well.
Let ∈ (), AR(, ) = (, 1, . . . , ), where ⇐ (,) 1 ⇐ (,) 2 ⇐ (,)
controlled by complete
LR(¢,$)-grammars.
In this section, we show that for any complete LR(¢,$)grammar obtained by the construction from the proof of same pumping analysis by reduction as .
Theorem 2. Let = (, Σ , , ) be a complete LR(¢,$)-grammar with an accepting grammar = (, Σ ∪ {¢, $}, , ) and a rejecting grammar =
∪ {¢, $}, , ). (, Σ an
Then there
exists a procedure that constructs scf-det-mon-RP-automaton ( )
= (, Σ , ¢, $, 0, , , A, R) such that AR( ( )) = AR( ),
AR(A, ( ))
= AR(R, ( )) = AR(R, ).
AR(A, ), and
Proof. The construction is based on the same idea as the
construction of the det-mon-R-automaton
simulating a syntactic analysis of a deterministic context-free
language in [
The second diference
here is that we use det-mon-RP-automata instead of det-mon-R-automata. Let us note that each det-mon-R-automaton can be easily converted into a det-mon-RP-automaton ′ by splitting each restarting instruction of into one preparing instruction and one restarting instruction of ′. 1
1 2
It is not hard to see from the previous construction that ( ) is an scf-det-mon-RP-automaton such that AR( ( )) = AR( ), AR(A, ( )) = AR(A, ), and AR(R, ( )) = AR(R, ).
The fact that ( ) is deterministic and monotone
follows from the construction of det-mon-R-automaton
in [
To see that the resulting det-mon-RP-automaton ( ) performs pumping analysis by reduction by , Definition 12. Let = (, ) be a complete we sketch the construction of ( ). LR(¢, $)-grammar with the corresponding accepting gram
By simulating a pumping analysis by reduction by mar and rejecting grammar . Let ( ) be the on a word ∈ {¢} · Σ * · { $}, we can construct the scf-det-mon-RP-automaton constructed by the construcderivation tree , according to grammar (the tion described in the proof of Theorem 2. inner vertices of which are labeled with nonterminals We say that ( ) is an RP-automaton with pumpand leaves correspond to terminal symbols). ing analysis by reduction according to , ( ) is
Thus, for any word ∈ {¢} · Σ * · { $} there is exactly an RP(LRG(¢,$))-automaton, and by ℒ( ((¢, $))) one derivation tree , by . Similarly, as in the we denote the class of all languages accepted by case of the standard pumping lemma for context-free RP((¢, $))-automata. Additionally, we say that languages, we can take = such that, for any () is the rejecting language of ( ), and we denote word of length greater than , there are (complete) it as ( ( )). subtrees 1 and 2 of , such that 2 is a subtree of 1 and the roots of both subtrees have the same label (cf. Corollary 1. For any LR(¢,$)-grammar there exists Fig. 4); in addition, 2 has fewer leaves than 1, 1 has a complete LR(¢,$)-grammar = (, ) and a deat most leaves, and |12| > 0. terministic monotone RP((¢, $))-automaton with a
Obviously, replacing 1 with 2, we get the derivation pumping analysis by reduction according to such that tree (0) for a shorter word (0) (if = 12 () = ( ( )), () = ( ( )). then (0) = ). Lemma 1. ℒ(det-mon-RP) ⊆ DCFL.
The key to the construction of ( ) is the
possibility to identify the leftmost sub-word 12 correspond- Proof. As the models of det-mon-R- and
det-mon-RPing to sub-trees 1 and 2 by , as shown in Fig. 4, automata difer only slightly, we can use here a
when reading from left to right with the help of a constant slightly modified proof of Lemma 8 in [
If no such pumping sub-tree is built over the contents Proof. The theorem is a consequence of the previous of the read/write window, the automaton ( ) for- lemma and the previous corollary. gets the leftmost of these sub-trees with all its ≥ 1 leaves, and reads new symbols to the right end of the 5. Conclusion and Future Work bufer (performing MVR-instructions). Then ( ) continues constructing the maximal sub-trees with all In this paper, we have introduced complete LR(¢,$)leaves in the (updated) bufer (again by simulating the grammars and restarting pumping RP(LRG(¢,$))LR(0) analyzer for ). automata. We have answered some basic questions
Short words of length less than are accepted/rejected concerning this type of automata and grammars. By in tail computations. simulating classical LR(0)-analysis for complete LR(¢,$)- [7] M. Procházka, Redukční automaty a syntaktické grammars, RP(LRG(¢,$))-automata can perform pumping chyby, Phd-thesis, Faculty of Mathematics and analysis by reduction for complete LR(¢,$)-grammars. Physics, Charles University, Prague, 2011. In Czech.
The constructions and results in this paper should enable to introduce and study regular and nonregular characteristics of two-sided pumping patterns of RP(LRG(¢,$))-automata and LRG(¢,$)-grammars and use such characteristics to prepare tools for localization of syntactic errors of general (and special) deterministic context-free languages. This way, we can extend and refine results from [7].
The research has been supported by the grant 1/0601/20 of the Slovak Scientific Grant Agency VEGA (Dana Pardubská) and the grant 19-21198S of the Czech Science Foundation (Daniel Průša).