The reducing automaton, a variant of the restarting automaton, is introduced and its normalizations are studied. They provide useful features such as prefix-correctness and state minimality. The LR(0) grammar generating the same language is constructed for any monotone reducing automaton. This grammar is used to construct an equivalent monotone reducing automaton that is prefix-correct . The minimization of a set of states of any reducing automaton using the method already invented in the theory of Moore machines is described. Both normalizations can be applied to the monotone reducing automaton sequentially so that the obtained automaton is both prefix-correct and state-minimal. reducing automata, LR(0) grammars, prefix-correctness, state-minimality Figure 1: Reducing automaton with a state in its control unit and a working head scanning an item of the working list This paper is a revised translation of the author's disser- at position 2 that contains a symbol +. The reducing automaton difers from the restarting au-
tation thesis [1]. Some parts are reworded, some supplemented, others omitted.
The reducing automaton (first mentioned in [ 2]), like its predecessor and ideal, the restarting automaton (see [3]), is a device suitable for describing a syntax of both formal and natural languages. It is based on the notion of reduction analysis, i.e., a gradual truncation of the analyzed string that preserves both its incorrectness and correctness1. The following example of a gradual simplification of the arithmetic expression a + ( ( a ) ) shows that the reduction analysis is quite natural.
a + ( ( a ) ) a + ( a + a tomaton in several details: 1. It lacks a fixed size lookahead window that is actually moved to the control unit. 2. The sequence of the head movement and the state change is reversed. 3. Positions of the reduced worklist items are precisely determined. It allows us to reuse some of the concepts and methods invented in standard grammar and automata theory and simplifies the techniques presented here: (a) construction of an LR(0)grammar that generates the same language as a given monotone reducing automaton (Section 3), (b) construction of an equivalent prefix-correct monotone reducing auITAT’22: Information technologies – Applications and Theory, Septem 0 1 2 + 3 4 ( 5 6 ) 7 ) 8 » state-minimal reducing automaton (Section 4). On the other hand the mentioned diferences does not prevent us to adopt results reached for restarting automata as any reducing automaton can be simulated by a restarting automaton and vice versa while preserving (combination of) properties like determinism or monotony. Here we focus on monotone reducing automata, which recognize deterministic context-free languages, as shown for their predecessors, deterministic monotone restarting automata in [3].
The reducing automaton is shown in Figure 1. It processes a finite list of items. The first and the last item of the list contains the delimiter « and » respectively. Any other ferent from both delimiters and a natural number, the position of the item in the list. The positions of the items from left to right form an increasing sequence. The positomaton, and (c) construction of a strongly equivalent item contains a symbol of the finite input alphabet difAttribution 4.0 International (CC BY 4.0).
© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License tion of any item does not change during the computation. CEUR htp:/ceur-ws.org ISN1613-073
CEUR
Workshop Proceedings (CEUR-WS.org)
The reducing automaton resembles a finite-state automa1Restarting automata preserve correctness if they are deterministic. ton. It consists of a control unit and a working head. At any given time the control unit is in one of the finitely where Σ is the finite input alphabet, «,» ∉ Σ is the left and right delimiter of an input word, respectively, is the ifnite set of transition states, 0 ∈ is the initial state, RED(101) is the finite set of final and reducing states, ∶ × (Σ ∪ {»}) ⟶ ( ∪ ) is the transition function. Sets and are disjunctive. optionally contains accepting and rejecting ifnal states ACC and ERR and finitely many reducing states 0 1 2 3 5 7 8 of a form RED() , where is a sequence of 0 and 1 that « a + ( a ) » begins with 1 ( ∈ 1 ⋅ (1|0)∗). 0 means “leave a symbol at a corresponding position in a working list”, 1 means “delete a symbol at a corresponding position from a working list ”.
If (, ) = ′, we say that the automaton moves from the state over the symbol to the new state ′, or also 0 that the transition function switches the control unit of the automaton from the state over the symbol to the new state ′.
We extend the transition function to the domain many states and the working head reads one item of the ( ∪ ∪ { RED}) × (Σ∗ ⋅ {, »}), where RED is the new auxiliary list. The automaton starts its computation in the initial state diferent from all states from and is an empty state with the head placed on the very first item of the word. We mark the new extended function as . The list containing the left delimiter «. At each step of the function equals to the transition function for all pairs computation the automaton moves its working head to (, ) ∈ × (Σ ∪ { »}). For any other pair from its domain the right onto the next item and changes its state accord- it is defined as follows: ing to the current state and the symbol contained in the scanned item of the list. The new state is determined by ( ACC, ) = ACC ( RED(), ) = RED a transition function. ( ERR, ) = ERR ( RED, ) = RED
Some states of the automaton are final , some others
are reducing. The final states are ACC, the accepting state, We define the reflexive and transitive closure ∗ of the
and ERR the rejecting state. Reaching the ACC state means function in the usual way. We consider only automata
ifnishing the computation and accepting the word con- with the extended transition function satisfying the
foltained in the working list. By switching into the ERR lowing conditions for any ∈ , ∈ Σ ∪ { »}, ′ ∈ ∪ ,
state, the automaton terminates the computation by re- and ∈ Σ ∗ ⋅ {, »}:
jecting the word being processed. RED() , ∈ 1 ⋅ (1|0)∗, is
the reducing state. Just after transition into this state, the (, ») = ′ ⟹ ′ ∈
automaton truncates the working list as prescribed by (, ») = RED() ⟹ 0 is the sufix of
the reducing sequence , moves its working head to the (, ) = ACC ⟹ = »
beginning of the working list, and transfers its control ∗( 0, ) = RED() ⟹ || ≥ ||
unit to the initial state. The reducing sequence deter- Characteristic constant of the automaton is the
mines items to be removed from the list in the following length of the longest binary sequence contained in
reway: If its -th symbol from the right equals to 1 then the ducing states of the automaton ,
automaton removes the -th item from the list counting
from the item under the working head to the left (count- ( ) = max {|| ∣ RED() ∈ } (
The truncation of the words (a), +a» by the reduction sequences 101, 110 respectively looks like this: / = ( 1 a 0 a ) 1 / = + 1 a 1 » 0 » « ′», Based on the reduction operation, we introduce reduction relation. This allows us to describe how the automaton successively rewrites the processed word ∈ Σ ∗. The reducing automaton reduces the word « » to the word
« » ⇒ « ′», Σ∗ ⋅ {, »}. Obviously, | | > | if ∗( 0, ) = RED() , » = , ′» = (/)⋅ ′| and the above reduction
for some ∈ is shortening. We refer to the reflexive and transitive closure of the reduction relation as ⇒∗ . By reduction analysis of the automaton
we mean any sequence of reductions
« 1» ⇒ « 2» ⇒ … ⇒ « », which cannot be extended further. If ∗( ») = ACC, we are talking about an accepting reduction analysis, otherwise it is a rejecting reduction analysis. We often use the shorter term analysis instead of reduction analysis. ing automaton in one stage form its simple language 0( ) =
{ ∈ Σ ∗ ∣ ∗( 0, ») = ACC}.
It is obvious that 0( ) is regular. We define the language accepted or also recognized by the reducing automaton as the set of all words over the alphabet Σ for which there exists an accepting analysis of the automaton , ( ) =
{ ∈ Σ ∗ ∣ « » ⇒∗ « ′» ∈ « 0( ) »}.
Let us assume that 1 = (Σ1, «, », 1, 1, 1, 1) and The words over the alphabet Σ accepted by the reduc- terministic monotone restarting automata (det-mon-R 1∗( 1, ) = ACC 1∗( 1, ) = ERR ⟺ 2∗( 2, ) = ACC ⟺ 2∗( 2, ) = ERR
Using the reduction relation, we can express a basic property of reducing automata called error and correctness preserving property.
Lemma 2.1. If « 1» ⇒ « 2», then 1 ∈ ( )
, if 2 ∈ ( )
. otherwise « 2» ⇒∗ « » ∈ « 0( ) ».
Proof. Let’s assume that « 1» ⇒
« 2». 1. If 2 ∈ 3.
For any mon-red-automaton , we construct a grammar
whose derivation trees correspond closely to computations of a given automaton . We show that this grammar generates the language recognized by the grammar , which is obtained by reducing the grammar = ( , , ,
), where = Σ ∪ { «, »} is the set of terminals; is the set || ≤ ( )
, ∈ Σ ∗ ⋅ {, »}, | | ≤ ( ) of nonterminals containing 5-tuples (, , , , ), ∈ Σ ∪ { «, »}, ∈ ∪ ( ⧵ {
ERR}), ∈ {,
«} ⋅ Σ∗ ⋅ {, »}, , and ∈ { ACC} ∪
where {RED() ∣ ∃ ′ ∶ RED( ′
) ∈ } ; = ( «, 0, , ACC, ) ∈ is the initial nonterminal; is the set of rules defined as and ∈ Σ ∪ { »}. (and therefore as well) is obviously rule → ∈ ⟹ ∈
→ ∈
(
with at least two maximum nonterminal paths. We show that the resulting tree is a derivation tree of the grammar .
Suppose that the first two maximum nonterminal paths of the tree , together with terminals they generate, are drawn in Figure 4a. Note that the vertex denoted by the nonterminal is the branching point of these nonterminal paths. We construct the tree ( )
in the following way:
′ 2. 2. Remove the vertices , … , 1. 3. For each ∈ {, … , 2} do the following: vertex ′ .
a) replace the vertex ′ with the vertex ′ b) add the terminal vertex ′, where ′ is the symbol in the first component of the nonterminal ′ c) add an edge from ′ to ′ 4. Add a horizontal edge from the vertex −1 to the Function converts the first two maximum nonterminal paths of the tree (including the terminals they generate) in Figure 4a to the path drawn in Figure 4b.
Lemma 3.1. For every derivation tree of the grammar
that lies in the domain of the function (contains at least two maximal nonterminal paths), the following statements hold:
→ ∈ ⟹
→ ∈ ⟹ =
→ ∈
and =
(
gives the word ′, then Proof. Suppose that the first two maximum nonterminal paths of the tree , together with the generated terminals, look like paths depicted in Figure 4a.
(i). It follows from (
The following rules are used in the first maximal
nonAccording to (
→ +1 ′ −1
→ −1 ′ is a rule of grammar . The following rules are used in the second maximal nonterminal path of the tree for some +1 , …, 2 ∈ ∪ {} :
′ → +′1 +1 −′1 → ′ ′ → ′
+′1 +1
⋮
⋮
′ 2−1 → ′ 2−1 ′ 2 2
′ 2 → ′ 2
According to (
′ → ′ ′ +1 +1 ⋮ ⋮ ′ 2−1 → ′ 2−1 ′ 2 2 ′ 2 → ′ 2 are rules of the grammar . The tree ( ) the derivation tree of the grammar .
(ii). The construction of the tree ( )
is therefore from the tree involves the removal of the sufix of the first nonterminal path just behind the branching point with the second nonterminal path. All other nonterminals are eventually replaced by other nonterminals, and all other edges between nonterminals in the tree remain unchanged. Thus, the derivation tree ( )
contains one less maximal nonterminal path than the derivation tree .
(iii). If the tree gives the word and its first two maximum nonterminal paths are shown in Figure 4a, then obviously
= 0 1 … +1 … 1 for some . The nonterminal is the last common nonterminal of the first two nonterminal paths of the tree and is rewritten to +1 ′ using the grammar rule. The definition of the grammar rule for each the state contained in the second component of the nonterminal , 1 = RED() for some reduction sequence is the state contained in the second component of the nonterminal 1, ( , , , , ) =
→ +1 = ( +1 , +1 , , RED(
Proof. If « ′» ⇒ word is a prefix of ′», ∗(, ) = « », then for some , , and the
RED() , and | | = || . ≥ |/| = way: Let 0 → 1 → … →
be the first maximal nonterminal path of the derivation tree and the first components of nonterminals on this path contain the terminal symbols «, 0, 1, …, . Since the automaton
is monotone, The tree ′ is obtained from the tree in the following and / =
1 … … , where = || . 1. Remove the terminal symbols , …, . 2. Replace each nonterminal , ≤ ≤ , on the ifrst nonterminal path with the nonterminals ′,
which we get from by replacing the empty word in the third component with the word … . 3. Add new nonterminals ″ = ( , , , , ) =
, +″ = ( , + , , RED( ′), / ), of length , ′ ∈ {1, … , | |} . ′ where is the -th symbol of the word from the left, ′ is the prefix of the word of length , = , ′ is the prefix of the reduction sequence = and +
= ( , ′) for all 4. Add a terminal and an edge from the ″ terminal to this terminal. Similarly, we add the terminals 1, …, || and connect them to the new derivation tree with an edge leading along the line from the +″1 , …, ″
+|| . …, ″ +||−1 → +||−1
+″|| . 5. We join the nonterminal ″ to the new derivation tree by an edge leading from the nonterminal −1 .
We use the grammar rules −1
″ ilarly, we join the nonterminals +1 → −1 ″
′. Sim, …, ″ +|| the derivation tree using the rules ″ → +″1 ,
to The above construction yields a derivation tree ′ which gives the word « ′» and ( ′
) = . We can check the correctness of this construction using the definition of nonterminals and the rules of the grammar . any words from « Σ∗ ». If at the same time Lemma 3.3. Let be any natural number, 1, …, be any derivation trees of the grammar , and 1, …, • 1 contains exactly one maximal nonterminal path, • +1 ⇒ for all ∈ 1, … , − 1 , nonterminal paths.
Proof. We prove the theorem by induction on the natural number . Obviously, contains just maximal maximal nonterminal path
= 1 . Let 1 be the derivation tree of the grammar , which gives the word 1 and contains exactly one 0 right-hand side is used in this tree. Thus, only the fol- Proof. We prove the theorem by induction on the natural lowing rules are used: • 1 is accepted by the automaton in a single stage. Lemma 3.4. Let be any natural number and 1, …, • +1 ⇒ for all ∈ {1, … , − 1} , • 1 is accepted by the automaton in a single stage. then for some derivation trees 1, …, of the grammar is empty (for all ∈ {1, … , } ) because it is empty in the initial nonterminal 0 and for all rules −1 →
| , the word in the third component of the nonterminal used in the tree 1: is not longer than the word in the third component of It follows that the nonterminal −1 . Thus, only the following rules are
−1 → | and the calculation tree 1 for the word 1 looks like this: « induction holds, so it also holds for the tree . with maximal nonterminal paths, and if it gives the word ′, then ⇒ ′. For the tree ′ the theorem by ( −1 , ) = .
= ( , , , ACC, ) nonterminal of the grammar and is the nonterminal of the grammar , 0 is the initial −1 → −1 → gives the word =
« 1 … −1 »: are the rules of the grammar . So we can construct the following derivation tree of the grammar , which « ↑ 0 1 ↑ be any word such that ′ ⇒ . Thus, by the induction assumption, some derivation tree of the grammar yields the word . Then, according to 3.2, there is a derivation tree ′ which gives the word ′ and =
′). So the theorem holds for the word ′, which the automaton accepts in + 1 stages.
The following theorem is a direct consequence of lemmata 3.3 and 3.4.
Theorem 3.1. ( ) = «( )
».
The next theorem says that the grammar of the monotone reducing automaton
is suitable for constructing a classical syntactic parser for the language recognized by this automaton.
Theorem 3.2. is an LR(0) grammar.
Proof. First, let us recall some classical notions introduced in the context of LR(0) grammars, as given, for example, in [4].
We call any expression of type → . , an item of the context-free grammar , where → is a rule of the grammar . In particular, → . is an item if Checking all types of rules of the grammar , we → is a rule of grammar . For each rule → , we get that the first two components of item’s characteristic call → . a complete item. We say that → . is a uniquely determine its third component. More precisely, valid item for the string if there exists a right sentential if ( 1,1, 1, 1,2) and ( 2,1, 2, 2,2) are characteristics of two form ( is a string of terminals) such that = . items of the grammar , then We use the notation () for the set of all valid items for the string . ( 1,1 = 2,1 and 1 = 2) ⟹ 1,2 = 2,2
A context-free grammar = ( , , , ) is called an LR(0) grammar if it satisfies the following conditions: A set of items has a continuous characteristic if 1. The initial symbol does not appear on the right
hand side of any rule. 2. No reduce/reduce conflict. For any string ∈ ( ∪ ) ∗, there is at most one complete item in the set ( ) . 3. No shift /reduce conflict. If a complete item occurs in ( ) , then there is no item with a terminal to the right of the dot in ( ) .
[ ] = {( 0, , 1), ( 1, , 2), … , ( −1 , , )} for some 0, 1, 2, …, −1 , and .
By verifying all types of rules of the grammar , we can prove the validity of the following statements, which say that construction of the states of the item automaton creates only sets of items with a continuous characteristic.
1. () has a continuous characteristic. if = (, , , , ) ∈ ⧵ {} for some and .
The characteristic of the strings formed by terminals and nonterminals of the grammar is defined by the following rule: The first condition is satisfied for grammar , because the initial nonterminal does not occur on the right-hand 2. If has a continuous characteristic, = → side of any rule of . . ∈ and = { → . ∣ → ∈ }, then
We prove the remaining two conditions using a method ∪ has a continuous characteristic. taken from [4] which is based on the notion of character- 3. If has a continuous characteristic, then for each istic. We define the characteristic sequentially, first for symbol of the grammar , the set = { → terminal and nonterminal symbols, then for strings of ter- . ∣ → . ∈ } also has a continuous minal and nonterminal symbols, then for item sets of the characteristic. grammar, and finally for item sets obtained by constructing the states of the item automaton of the grammar . Thus, any state ( ) has a continuous characteristic. The We show that each item set that is a state of the item definition of a set of items with continuous characterisautomaton has a continuous characteristic, which results tic implies that such a set can contain at most one triple in the absence of both types of conflicts. whose third component is empty or terminal. Each com
For each terminal or nonterminal symbol of grammar plete item → . has characteristic ([], , empty), and , we define the characteristic [] of the symbol as each item → . containing a terminal to the right follows: of the dot has characteristic ([], , terminal). There⎧initial, if = , fore, any set of items with a continuous characteristic [] = ⎪terminal, if ∈ cnaonlocnognetaricnoanttaminosstanonyeitceommwpliethteaitteemrm, ainnadl itfoitthdeoreisg,hitt ⎨⎪(, , ), of the dot. ⎩ Thus, each set ( ) satisfies the second and third conditions of the definition of LR(0) grammar and is an
LR(0) grammar.
empty, if = , [ ] = {[], if ∈ ∪ for some ′.
and =
′
the first nonterminal path of any of grammar’s derivation tree uses rules of types listed in the first row only, i.e. the Normalized mon-red-automata form a subclass of reduc- rules with the right hand side starting with the terminal. ing automata. A normalized mon-red-automaton is any Thus, the last rule used in the first maximal nonterminal mon-red-automaton that is both prefix-correct and state path of any derivation tree of grammar is of type → minimal. In this section, we show how to construct an , and the first complete item encountered by the item equivalent normalized mon-red-automaton to any mon- automaton is of type → .. Therefore, we construct red-automaton that accepts a non-empty language. the states of the reducing automaton ′ only from the
We use a grammar of mon-red-automaton constructed following types of items in the previous section to construct an equivalent prefixcorrect mon-red-automaton. Then we show how to min- → . → . → . imize the set of states of any red-automaton including → . → . → . the elimination of unreachable states. and we consider the transitions between item sets over 4.1. Prefix-correctness terminal symbols only.
Now let us describe a construction of the prefix-correct Suppose that = (Σ, «, », , 0, , ) is a monotone re- automaton using just mentioned principles. For any ∈ ducing automaton. We say that is prefix-correct if for Σ∗ and ∈ Σ ∪ { «, »} we define the item sets using the any word ∈ Σ ∗ and reduction sequence the following following rules implications hold: ∗( 0, ) ∈ ⟹ ∃ ∈ Σ
∗ ∶ ∈ ( ) ∗( 0, ) = RED() ⟹ ∃ ∈ Σ ∗ ∶ ∈ ( ) ∗( 0, ») = RED() ⟹ ∈ ( ) where is the starting nonterminal of the grammar .
The first two implications say that any word ∈ Σ ∗, over We obtain the above item sets utilizing slightly modified which the automaton moves its working head while method already used in classical theory of parsing to switching its control unit from the initial state 0 to any construct an item automaton for a given LR(0) grammar. transition or reducing state, is a prefix of some word from Here, we consider only items of the above types. Thus, the language ( ) . The third implication states that any our item sets are subsets of states of the classical item word » ∈ Σ∗ », over which the automaton moves automaton, and hence contain neither shift /reduce nor reits working head while switching its control unit from duce/reduce conflict. A set of all nonterminal states of the the initial state 0 to any reducing state, is a word of the reducing automaton ′ consists of all constructed item language ( ) ». However, the automaton may need a sets except () and sets containing only a complete item. few more stages to formally accept it. Its initial state is the set ( «). The reducing states are just all RED() for which there exists a complete item → .
Theorem 4.1. For each mon-red-automaton, an equiva- of the grammar ( ′) and = (, RED(), , RED(), ) . lent prefix-correct mon-red-automata can be constructed. We define the transition function as follows: () = { → () = { → . « ∣ →
« ∈ }, . ∣ → ∪ { → . ∣ →
a → ∈ }, . ∈ ()} . ∈ () Proof. Suppose that = (Σ, «, », , 0, , ) is a monred-automaton. First, we construct an LR(0) grammar . Next, we construct a reducing automaton ′ = (Σ, «, », ′, 0′, ′, ′) based on the grammar . Finally, we show that ′ is monotone, prefix-correct, and equivalent to the original reducing automaton .
Construction of the reducing automaton ′ resembles a construction of an item automaton for the grammar . Transition states of the automaton ′ are defined as sets of items of this grammar, in the same way as in case of an item automaton. However, we are interested in those grammar rules only that can be used in the first nonterminal path of ’s derivation tree. While the grammar contains rules of the following types otherwise.
Equivalence of automata ′ and . «( ) » = ( ). We show that
Apparently, ( ) = «(
′)».
Suppose that « » ∈ ( ) and is the derivation tree of the grammar , which gives « ». By induction on the number of maximal nonterminal paths in the tree the left column from the sets ( «), …, ( « ) and then use (
′). , we prove that ∈ (
′).
If the tree contains only one maximal nonterminal path, then ( « ») = { →
» . } and = (», ACC, , ACC, ) , so ′∗( ( «), ») = ACC and thus ∈
Assume that the statement holds for all derivation trees of the grammar
with at most maximal nonterminal paths. We then prove that it also holds for derivation trees with + 1
maximal nonterminal paths. If is a derivation tree with + 1
maximal nonterminal paths, which gives the word « », then by Lemma 3.3, ( )
is a tree with maximal nonterminal paths that yields the assumption ′ ∈ ( word « ′» such that « » ⇒ ′). Thus, ∗( 0, ) =
« ′». By the induction and « » ⇒ ′ « ′». Therefore ∈ ( some prefix
« nonterminals in +1 +1 can be rewritten into some terminal strings, so that is a prefix of some word from would generate a word outside «Σ∗») and ∈ ( )
Monotony. Suppose the automaton ′ moves from
». the state ( «) via the prefix
of the word » to the state RED() ∈ ′, | | = || , and that the word consists of the symbols 1, …, ∈ Σ and the word consists of the symbols +1 , …, −1 ∈ Σ, ∈ Σ ∪ {»}. As in the proof of prefix correctness, we can now select the items listed in
« . If ⇒∗ their rules in the derivation listed in the right column: is reduced, some terminal string can be derived from 0. Suppose that / =
1 … . From the definition of the grammar , it follows that some of its nonterminals )) 1, 2, …, contain the symbols 1, 2, …, in their ifrst component, and the grammar contains the following → +1 0 0 → 1 1′ 1 → 2 2′ reduction analysis and, moreover, visited working list positions in each stage.
Suppose = (Σ, «, », , state machine with an alphabet Σ ∪ {»}, a set of states ∪ ∪ { RED}, an initial state 0, a set of final states , and a transition function . Thus, we can use the construction of a finite-state machine containing only reachable states from the theory of finite-state machines.
Let 1
= (Σ, «, », 2, 2, 2, 2) the same input alphabet Σ.
(Σ, «, », 1, 1, 1, 1) and 2 be reducing automata
= with
We define the relation ∼ ⊆ 1 × 2 in the following way: ∼ ′, if for each follows that 1∗(, ) = word ∈ Σ ∗ ⋅ {, »} from 1∗(, ) ∈ 2∗( ′, ) . If 1 = 2, then the
1 or 2∗( ′, ) ∈ 2 it relation ∼ is the equivalence on the set of transition states 1 of the automaton 1. We call the transition states, that are in the relation ∼, stage-equivalent. We call reducing automata 1 and 2 stage-equivalent, if their initial states are stage-equivalent ( 1 ∼ 2). Two stage-equivalent reducing automata either both accept, both reject, or both reduce any word, in all three cases at the same place in the working list, and in the case of reduction also according to the same reduction sequence.
Thus, any two stage-equivalent reducing automata are obviously strongly equivalent and vice versa. Since the stage equivalence and strong equivalence name the same phenomenon, we henceforth use only the term strong equivalence.
Let
be any reducing automaton. An automaton is state minimal if (i) all its states are reachable, and (ii) no its diferent transition states are equivalent. A reducing automaton ′ is called a reduct of a reducing automaton if (i) ′ is strongly equivalent to , and (ii) ′ is state minimal. machine that marks any word in the same way as the in the following way: output function, marks in the input word whether and where to accept, reject or reduce it (and how to reduce it) in the same way as the reducing automaton . We then construct its reduct ′ (with the same behaviour as ) and finally convert it back to the reducing automaton .
The Moore machine =
( , , Σ , Γ , , ), where is a set of states, is an initial state, Σ is an input alphabet, Γ is an output alphabet, is a transition function, and is an output function, is defined = ∪ ∪ { RED} = 0 Σ = Σ ∪ {»} Γ = ∪ { RED} ∪ { 0} = () = { 0, if ∈ ,
if ∈ ∪ { RED}
Finally, we move from the reduct ′ back to the reducing automaton ′ = (Σ′, «, », ′, 0′, ′, ′) defined as Σ′ = Σ ′ ⧵ {»} = Σ ⧵ {»} = Σ ′ = { ∣ ′() = 0} 0′ = ′ = = 0 ′ = { ′ ∈ ∣ ∃ ∈ ′ ∶ ′ = ′()} ′(, ) = { ′ ,
if ′ = ′(, ) ∈ ′ ′( ′), if ′ = ′(, ) ∉ ′
Now it is not hard to see that the constructed reducing automaton ′ is a reduct of the automaton .
The strong equivalence of the reducing automata and ′ follows from the following facts: 1. The set ′ contains exactly all reachable final or reducing states of the reducing automaton . 2. The initial state ′ of the Moore machine ′ is behaviorally equivalent to the initial state of the Moore machine . Thus, for any word ∈ Σ ∗ ⋅ {, »} and the reachable reducing state RED() holds:
′∗( 0′, ) = RED() ′( ∗′( ′, ) ) = RED() ( ∗ ( , ) ) = RED() function over a word contained in a working list to de- of the reducing automaton , the following equivalence original machine . So the idea is to design a Moore state RED() with the accepting or rejecting states ACC or machine for a reducing automaton which, by its
The state-minimality of the automaton ′ follows directly from the state-minimality of Moore machine ′ and from the way we obtained the automaton ′ from the machine ′. The reducing automaton ′ is therefore a reduct of the reducing automaton .
We say that reducing automata and ′ with the same alphabet Σ are isomorphic if there is a one to one mapping ℎ,
Theorem 4.4. Any two reducts of the same reducing automaton are isomorphic.
This theorem can obviously be proved by modifying the proof of the same theorem for Moore machines.
Corollary 4.1. No reducing automaton has fewer states than its reduct.
As the reduct is strongly equivalent to the reducing automaton for which it is constructed, the construction retains both monotony and prefix-correctness. So, for any monotone reducing automaton we can construct an equivalent monotone reducing automaton, which is both prefix-correct and state-minimal.
We introduced the reducing automaton and described two of its normalizations. Further, we plan to propose a construction of an equivalent mon-red-automaton with only repeatable reductions. A reduction is repeatable if « » ⇒ implies « +1 +1 » ⇒ « » for each ∈ ℕ 0. Further, we would like to distinguish repeatable reductions reducing regular contexts (either or is empty) and linear contexts (neither nor is empty) and normalize a monotone reducing automaton so that it reduces regular contexts from the right.
This paper was created as part of the Parsing and Syntactic Analysis seminar led by František Mráz and Martin Plátek at the Faculty of Mathematics and Physics of Charles University in Prague.