Following some previous studies on list automata and restarting automata, we introduce a generalized and refined model - the h-lexicalized restarting list automaton (LxRLAW). We argue that this model is useful for expressing transparent variants of lexicalized syntactic analysis, and analysis by reduction in computational linguistics. We present several subclasses of LxRLAW and provide some variants and some extensions of the Chomsky hierarchy, including the variant for the lexicalized syntactic analysis. We compare the input languages, which are the languages traditionally considered in automata theory, to the so-called basic and h-proper languages. The basic and h-proper languages allow stressing the transparency of h-lexicalized restarting automata for a superclass of the context-free languages by the so-called complete correctness preserving property. Such a type of transparency cannot be achieved for the whole class of contextfree languages by traditional input languages. The transparency of h-lexicalized restarting automata is illustrated by two types of hierarchies which separate the classes of infinite and the classes of finite languages by the same tools.
Chomsky introduced his well-known hierarchy of
grammars to formulate the phrase-structure (immediate
constituents) syntax of natural languages. However, the
syntax of most European languages (including English) is
often considered as a lexicalized syntax. In other words,
the categories of Chomsky are bound to immediate
constituents (phrases), while by lexicalized syntax they are
bound to individual word-forms. In order to give a general
theoretical basis for lexicalized syntax that is comparable
to the Chomsky hierarchy, we follow some previous
studies of list and restarting automata (see [
Analysis by reduction is a technique for deciding the correctness of a sentence. It is based on a stepwise simplification by reductions preserving the (in)correctness of the sentence until a short sentence is obtained for which it is easy to decide its correctness. Restarting automata were introduced as an automata model for analysis by reduction. While modeling analysis by reduction, restarting automata are forced to use very transparent types of computations. Nevertheless, they still can recognize a proper superset of the class of context-free languages (CFL). The first observation, which supports our argumentation, is that LxRLAW allow characterizations of the Chomsky hierarchy for classes of languages and for h-syntactic analysis as well.
An LxRLAW M is a device with a finite state control and a read/write window of a fixed size. This window can move in both directions along a tape (that is, a list of items) containing a word delimited by sentinels. The LxRLAWautomaton M uses an input alphabet and a working alphabet that contains the input alphabet. Lexicalization of M is given through a morphism which binds the individual symbols from the working alphabet to symbols from the input alphabet. M can decide (in general non-deterministically) to rewrite the contents of its window: it may delete some items from the list (moving its window in one or the other direction), insert some items into the list, and/or replace some items. In addition, M can perform a restart operation which causes M to place its window at the left end of the tape, so that the first symbol it contains is the left border marker, and to reenter its initial state.
In the technical part we adjust some known results to results on several subclasses of LxRLAW that are obtained by restricting its set of operations to certain subsets, and we also provide some variants and extensions of the Chomsky hierarchy of languages. E.g., an LxRLAI uses an input alphabet only.
We recall and newly introduce some constraints that are suitable for restarting automata, and we outline ways for new combinations of constraints, and more transparent computations.
Section 2 contains the basic definitions. The characterizations of the Chomsky hierarchy by certain types of LxRLAW is provided in Section 3.
In Section 4 we introduce RLWW-automata as a restricted type of LxRLAW and give several new constraints for them. By the basic and h-proper languages we show the transparency of h-lexicalized restarting automata through the so-called complete correctness preserving property. Using the new constraints and the basic and h-proper languages, we are able to separate classes of finite languages in a similar way as the classes of infinite languages and establish in this way new hierarchies, which can create a suitable tool for the classification of syntactic phenomena for computational linguistics. The paper concludes with Section 5. 2
In what follows, we use ⊂ to denote the proper subset relation. Further, we will sometimes use regular expressions instead of the corresponding regular languages. Finally, throughout the paper λ will denote the empty word and N+ will denote the set of all positive integers.
An h-lexicalized two-way restarting list automaton, LxRLAW for short, is a one-tape machine M = (Q, Σ, Γ, c, $, q0, k, δ , h), where Q is the finite set of states, Σ is the finite input alphabet, Γ is the finite working alphabet containing Σ, the symbols c, $ 6∈ Γ are the markers for the left and right border of the work space, respectively, h : Γ ∪ {c, $} → Σ ∪ {c, $} is a mapping creating a (letter) morphism from cΓ∗$ to cΣ∗$ such that, for each a ∈ Σ ∪ {c, $}, h(a) = a; q0 ∈ Q is the initial state, k ≥ 1 is the size of the read/write window, and
δ : Q × PC ≤k → P((Q × ({MVR, MVL} ∪ {W(v), SR(v), SL(v), I(v)})) ∪ {Restart, Accept, Reject}) is the transition relation. Here P(S) denotes the powerset of a set S,
PC ≤k := (c · Γk−1) ∪ Γk ∪ (Γ≤k−1 · $) ∪ (c · Γ≤k−2 · $), is the set of possible contents of the read/write window of M, and v ∈ PC ≤n, where n ∈ N.
According to the transition relation, if M is in state q and sees the string u in its read/write window, it can perform nine different steps, where q0 ∈ Q: 1. A move-right step (q, u) −→ (q0, MVR) assumes that (q0, MVR) ∈ δ (q, u) and u 6= $. It causes M to shift the read/write window one position to the right and to enter state q0. 2. A move-left step (q, u) −→ (q0, MVL) assumes that (q0, MVL) ∈ δ (q, u) and u 6∈ c · Γ∗ · {λ , $}. It causes M to shift the read/write window one position to the left and to enter state q0. 3. A rewrite step (q, u) −→ (q0, W(v)) assumes that (q0, W(v)) ∈ δ (q, u), |v| = |u|, and the sentinels are at the same positions in u and v (if at all). It causes M to replace the contents u of the read/write window by the string v, and to enter state q0. The head does not change its position. 4. An S-right step (q, u) −→ (q0, SR(v)) assumes that (q0, SR(v)) ∈ δ (q, u), v is shorter than u, containing all sentinels in u. It causes M to replace u by v and to enter state q0; the new position of the head is on the first item ofv (the contents of the window is thus ‘completed’ from the right; the positional distance to the right sentinel decreases). 5. An S-left step (q, u) −→ (q0, SL(v)) assumes that (q0, SL(v)) ∈ δ (q, u), v is shorter than u, containing all sentinels in u. It causes M to replace u by v, to enter state q0, and to shift the head position by |u| − |v| items to the left – but to the left sentinel c at most (the contents of the window is ‘completed’ from the left; the distance to the left sentinel decreases if the head position was not already at c). 6. An insert step (q, u) −→ (q0, I(v)) assumes that (q0, I(v)) ∈ δ (q, u), u is a proper subsequence of v (keeping the obvious sentinel constraints). It causes M to replace u by v (by inserting the relevant items), and to enter state q0. The head position is shifted by |v| − |u| to the right (the distance to the left sentinel increases). 7. A restart step (q, u) −→ Restart assumes that Restart ∈ δ (q, u). It causes M to place its read/write window onto the left end of the tape, so that the first symbol it sees is the left border marker c, and to reenter the initial state q0. 8. An accept step (q, u) −→ Accept assumes that
Accept ∈ δ (q, u). It causes M to halt and accept. 9. A reject step (q, u) −→ Reject assumes that Reject ∈ δ (q, u). It causes M to halt and reject.
A configuration of M is a string αqβ where q ∈ Q, and either α = λ and β ∈ {c} · Γ∗ · {$} or α ∈ {c} · Γ∗ and β ∈ Γ∗ · {$}; here q represents the current state, αβ is the current contents of the tape, and it is understood that the head scans the first k symbols of β or all of β when |β | < k. A restarting configuration is of the form q0cw$, where w ∈ Γ∗; if w ∈ Σ∗, then q0cw$ is an initial configuration. We see that any initial configuration is also a restarting configuration. Any restart transfersM into a restarting configuration.
In general, the automaton M is non-deterministic, that is, there can be two or more steps (instructions) with the same left-hand side (q, u), and thus, there can be more than one computation for an input word. If this is not the case, the automaton is deterministic.
A computation of M is a sequence C = C0,C1, . . . ,Cj of configurations, whereC0 is an initial configuration and Ci+1 is obtained by a step of M from Ci, for all 0 ≤ i < j.
An input word w ∈ Σ∗ is accepted by M, if there is a computation which starts with the initial configuration q0cw$ and ends by executing an Accept instruction. By L(M) we denote the language consisting of all input words accepted by M; we say that M accepts the input language L(M).
A basic (or characteristic, or working) word w ∈ Γ∗ is accepted by M, if there is a computation which starts with the restarting configuration q0cw$ and ends by executing an Accept instruction. By LC(M) we denote the language consisting of all basic words accepted by M; we say that M accepts the basic (characteristic) language LC(M).
Further, we take LhP(M) = { h(w) ∈ Σ∗ | w ∈ LC(M) }, and we say that M recognizes (accepts) the h-proper language LhP(M).
Finally, we take LA(M) = { (h(w), w) | w ∈ LC(M) } and we say that M determines the h-syntactic analysis LA(M).
We say that, for x ∈ Σ∗, LA(M, x) = { (x, y) | y ∈ LC(M), h(y) = x } is the h-syntactic analysis for x by M. We see that LA(M, x) is non-empty only for x ∈ LhP(M).
In the following we only consider finite computations of LxRLAW-automata, which finish either by an accept or by a reject operation.
An LxRLAI M is an LxRLAW for which the input alphabet and the working alphabet are equal.
For each LxRLAI-automaton M, L(M) = LC(M) = LhP(M). – Cycles, tails: Any finite computation of an LxRLAWautomaton M consists of certain phases. Each phase starts in a restarting configuration. In a phase called acycle, the window moves along the tape performing non-restarting operations until a Restart operation is performed and thus a new restarting configuration is reached. If after a restart configuration no further restart operation is performed, any finite computation necessarily finishes in a halting configuration – such a phase is called a tail. – Cycle-rewritings: We use the notation q0cu$ `cM q0cv$ to denote a cycle of M that begins with the restarting configuration q0cu$ and ends with the restarting configuration q0cv$. Through this relation we define the relation of cycle-rewriting by M. We write u ⇒cM v iff q0cu$ `cM q0cv$ holds. The relation u ⇒cM∗ v is the reflexive and transitive closure of u ⇒cM v.
We point out that the cycle-rewriting is a very important feature of LxRLAW. – Reductions: If u ⇒cM v is a cycle-rewriting by M such that |u| > |v|, then u ⇒cM v is called a reduction by M. 2.1
Here we introduce some constrained types of rewriting steps which assume q, q0 ∈ Q and u ∈ PC ≤k.
A delete-right step (q, u) → (q0, DR(v)) is an S-right step (q, u) → (q0, SR(v)) such that v is a proper subsequence of u, containing all the sentinels from u (if any).
A delete-left step (q, u) → (q0, DL(v)) is an S-left step (q, u) → (q0, SL(v)) such that v is a proper sub-sequence of u, containing all the sentinels from u (if any).
A contextual-left step (q, u) → (q0, CL(v)) is an S-left step (q, u) → (q0, SL(v)), where u = v1u1v2u2v3 and v = v1v2v3 for some v1, u1, v2, u2, v3, such that v contains all the sentinels from u (if any).
A contextual-right step (q, u) → (q0, CR(v)) is an Sright-step (q, u) → (q0, SR(v)), where u = v1v2v3 and v = v1v3 for some v1, v2, v3, such that v contains all the sentinels from u (if any).
Note that the contextual-right step is not symmetrical to the contextual-left step. We will use this fact in Section 4.
The set OG = {MVL, MVR, W, SL, SR, DL, DR, CL, CR, I, Restart} represents the set of types of steps, which can be used for characterizations of subclasses of LxRLAW. This set does not contain the symbols Accept and Reject, corresponding to halting steps, as they are used for all LxRLAW-automata. Let T ⊆ OG. We denote by T-automata the subset of LxRLAW-automata which only use transition steps from the set T ∪ {Accept, Reject}. For example, {MVR, W}-automata only use move-right steps, W-steps, Accept steps, and Reject steps.
Notations. For brevity, the prefix det- will be used to
denote the property of being deterministic. For any class
A of automata, L (A ) will denote the class of input
languages that are recognized by automata from A , LC(A )
will denote the class of basic languages that are
recognized by automata from A , and LhP(A ) will denote the
class of h-proper languages that are recognized by
automata from A . Moreover, LA(A ) will denote the class
of h-syntactic analyses that are determined by automata
from A . Let us note that we use the more simple notation
LP(A ) in [
For a natural number k ≥ 1, L (k-A ) (LC(k-A ) or LhP(k-A )) will denote the class of input (basic or hproper) languages that are recognized by those automata from A that use a read/write window of size k. – Monotonicity of Rewritings. We introduce various notions of monotonicity as important types of constraints for computations of LxRLAW-automata.
Let M be an LxRLAW-automaton, and let C = Ck,Ck+1, . . . ,Cj be a sequence of configurations of M, where Ci+1 is obtained by a single transition step of M from Ci, k ≤ i < j. We say that C is a sub-computation of M.
Let RW ⊆ {W, SR, SL, DR, DL, CR, CL, I}. Then we denote by W(C, RW ) the maximal (scattered) sub-sequence of C, which contains those configurations fromC that correspond to RW -steps (that is, those configurations in which a transition step of one of the types from the set RW is applied). We say that W(C, RW ) is the working sequence of C determined by RW .
Let C be a sub-computation of an LxRLAWautomaton M, and let Cw = cαqβ $ be a configuration from C. Then |β $| is the right distance of Cw, which is denoted by Dr(Cw), and |cα| is the left distance of Cw, which is denoted by Dl (Cw).
We say that a working sequence W(C, RW ) = (C1,C2, . . . ,Cn) is RW -monotone (or RW -right-monotone) if Dr(C1) ≥ Dr(C2) ≥ . . . ≥ Dr(Cn).
A sub-computation C of M is RW -monotone if W(C, RW ) is RW -monotone. If we write (right-)monotone, we actually mean {W, SR, SL, DR, DL, CR, CL, I}-right-monotone, that is, monotonicity with respect to any type of (allowed) rewriting and inserting for the corresponding type of automaton. By completely(-right)monotone, we actually mean monotone with respect to each configuration of the computation.
For each of the prefixes X ∈ {RW, λ , completely} we say that M is X-monotone if each of its (sub)computations is X-monotone.
Fact 2. Let M be an {MVR, SR, SL, W, I}-automaton. Then M is completely-monotone.
Remark on PDA. It is not hard to see that a 1{MVR, SR, SL, W, I}-automaton is a type of normalized pushdown automaton. The top of the pushdown is represented by the position of the head, and the content of the pushdown is represented by the part of the tape between the left sentinel and the position of the head. In fact, in a very similar way the pushdown automaton was introduced by Chomsky. A k-{MVR, SR, SL, W, I}-automaton can be interpreted as a pushdown automaton with a klookahead, and with a limited look under the top of the pushdown at the same time. (det-)PDAs can be simulated even by (det-)1-{MVR, SL, W}-automata. In the following, we will consider the automata which fulfill the condition of completely-right-monotonicity for pushdown automata (PDA). 3
We transform and enhance some results from [
det-{MVR}- and {MVR}-automata work like deterministic and nondeterministic finite-state automata, respectively. The only difference is that such automata can accept or reject without visiting all symbols of an input word. Nevertheless, these automata can be simulated by deterministic and nondeterministic finite-state automata, respectively, which instead of an Accept-step enter a special accepting state in which they scan the rest of the input word. Since the regular languages are closed under homomorphisms, we have the following proposition. Proposition 3. For X ∈ {L , LC, LhP}, the classes X (1-det-{MVR}) and X (1-{MVR}) coincide with the class REG of regular languages.
Observe that for LxRLAW-automata with window size 1, the operation SR coincides with the operations DR and CR, and that the operation SL coincides with the operations DL and CL, and that in this situation all these operations just delete the symbol currently inside the window.
X ({MVR, CL, W}) ⊆ CFL, where CFL is the class of context-free languages. Proof. Any {MVR, CL, W}-automaton M = (Q, Σ, Γ, c, $, q0, k, δ , h) can be simulated by a pushdown automaton (PDA) P which stores the current content of the window of M in its control unit (as a state). On an input word w, P first tries to read the firstk symbols of w and to store them within its control unit. If w is of length less than k, then P accepts or rejects w upon encountering the right sentinel $. Otherwise, P continues while preserving the following invariant: the contents of the pushdown store of P equals the part the tape of M to the left of its current position, the contents of the window of M and its state are both stored in the control unit of P, and the rest of the tape of M to the right of its window is the unread part of the input of P.
Hence, P accepts exactly L(M) by entering an accepting state and reading the rest of its input whenever M performs an Accept-step. If we include all working symbols of M into the input alphabet of P, we obtain a PDA P0 such that L(P0) = LC(M), thus the basic language of M is contextfree. As CFL is closed under homomorphisms, also the h-proper language of M is context-free, too.
X (1-{MVR, CL, W}) coincides with the class CFL of context-free languages.
Proof. According to Proposition 4, each language accepted by a 1-{MVR, CL, W}-automaton as an input language or as a basic language is context-free. It remains to proof the opposite inclusion. Let L be a context-free language. Clearly, the empty language and the language {λ } can be accepted by a 1-{MVR, CL, W}-automaton.
W.l.o.g. we can suppose that L \ {λ } is generated by a context-free grammar G = (Π, Σ, S, PG) in Chomsky normal form. We can construct a PDA P accepting the language L \ {λ } by empty store. For each nonempty word w ∈ L, the PDA P can guess and simulate a rightmost derivation of w according to G in reverse order. That is, P will perform a bottom-up analysis of w which uses a shift-operation that moves the next input symbol onto the pushdown and reductions according to the rewrite rules from PG. The reduction according to a rule of the form X → x, for X ∈ Π, x ∈ Σ, consists of popping x from the top of the pushdown and pushing X onto the pushdown. The reduction according to a rule of the form X → Y Z, where X ,Y, Z are nonterminals of G, consists of popping Y Z (in reversed order) from the pushdown and pushing X onto the pushdown.
The empty word λ can be immediately accepted or rejected by a 1-{MVR, CL, W}-automaton M when λ ∈ L or λ 6∈ L, respectively. For each nonempty word w ∈ Σ∗, each computation of P on w can be simulated by M in such a way that the top of the pushdown will be in the window of M. The rest of the contents of the pushdown of P will be stored on the part of the tape of M to the left of the position of its window.
A shift-operation of P can be simulated by a MVR-step. The reduction according to a rule of the form X → x, for X ∈ Π, x ∈ Σ, will be simulated by the W-step which rewrites x in the window of M by X . The reduction according to a rule of the form X → Y Z, where X ,Y, Z ∈ Π, will be simulated by the CL-step which deletes the tape cell containing Z and a W-step which rewrites the symbol Y in the window of M by X . As P accepts when the pushdown contains the single symbol S, M will perform an Accept-step, when the only symbol on its tape is the initial nonterminal S. Clearly, L(M) = L(P). Additionally, M can check that after each MVR-step the symbol which appears within its window is either the sentinel $ or a terminal from Σ. In this way it is ensured that M does not accept any word containing a working symbol, hence LC(M) = LhP(M) = L.
It is easy to see that a linear-bounded automaton working on a tape containing an input word delimited by sentinels directly corresponds to a 1-{MVR, MVL, W}automaton. We can also see that a {MVR, MVL, W}automaton can be simulated by a 1-{MVR, MVL, W}automaton. Recall that the class CSL is closed under nonerasing homomorphisms. Therefore, we have the following statement.
X ({MVR, MVL, W}) coincides with the class CSL of context-sensitive languages.
By adding the ability to insert cells within the working tape to the operations MVR, MVL and W, we can easily simulate an arbitrary Turing machine. Hence we have the following proposition.
X ((det-){MVR,MVL,W,I}) coincides with the class RE of recursively enumerable languages.
From the previous results we obtain the following variant of the Chomsky hierarchy for the classes of the hsyntactic analysis which follows from the corresponding hierarchies for the classes of h-proper and basic languages. Corollary 1. We have the following hierarchy: LA({MVR}) ⊂ LA({MVR, CL, W}), LA({MVR, CL, W}) ⊂ LA({MVR, MVL, W}), LA({MVR, MVL, W}) ⊂ LA({MVR, MVL, W, I}).
In a similar way we can obtain the deterministic variants of the Chomsky hierarchy. 4
Here we formulate the h-lexicalized two-way restarting
automaton in weak accepting (cyclic) form, and some of
its subclasses. By considering basic and h-proper
languages, this new type of automaton is close to the method
of analysis by reduction (see [
An h-lexicalized two-way restarting automaton in weak accepting form (originally called cyclic form) M, an hRLWW-automaton for short, is a {MVR, MVL, SL, SR, Restart}-automaton, which uses an SL-step or SR-step exactly once in each cycle (only one of them), and directly accepts only words that fit into its window.
An hRLWW-automaton is called an hRLW-automaton if its working alphabet coincides with its input alphabet. Note that in this situation, each restarting configuration is necessarily an initial configuration.
An hRLW-automaton is called an hRL-automaton if each of its rewrite steps is a DL- or DR-step.
An hRL-automaton is called an hRLC-automaton if each of its rewrite steps is a CL- or CR-step.
An hRLWW-automaton is called an hRLWWCautomaton if each of its rewrite steps is a CL-step or CRstep.
An hRLWW-automaton is called an hRRWWautomaton if it does not use any MVL-steps. Analogously, we obtain hRRW-automata, hRR-automata, and hRRCautomata.
We see that for hRLWW-automata, all cycle-rewritings are reductions. We also have the following simple facts, which illustrate the transparency of computations of hRLWW-automata due their basic and h-proper languages.
Let M be a deterministic hRLWW-automaton, let C = C0,C1, · · · ,Cn be a computation of M, and let cui$ be the tape contents of the configuration C i, 0 ≤ i ≤ n. If ui ∈ LC(M) for some i, then u j ∈ LC(M) for all j = 0, 1, . . . , n.
Let M be a deterministic hRLWW-automaton, let C = C0,C1, · · · ,Cn be a computation of M, and let cui$ be the tape contents of the configuration C i, 0 ≤ i ≤ n. If ui 6∈ LC(M) for some i, then u j 6∈ LC(M) for all j = 0, 1, . . . , n.
Let M be an hRLWW-automaton, let C = C0,C1, · · · ,Cn be a computation of M, and let cui$ be the tape contents of the configuration C i, 0 ≤ i ≤ n. If ui ∈ LC(M) for some i, then u j ∈ LC(M) for all j ≤ i.
Let M be an hRLWW-automaton, let C = C0,C1, · · · ,Cn be a computation of M, and let cui$ be the tape contents of the configuration C i, 0 ≤ i ≤ n. If ui ∈/ LC(M) for some i, then u j 6∈ LC(M) for all j ≥ i.
For each hRLW-automaton M, L(M) = LC(M) = LhP(M).
From the last corollary above, the Complete Error and Complete Correctness Preserving Properties for deterministic hRLW-automata, and the Suffix Error Preserving Property and the Prefix Correctness Preserving Property for hRLW-automata follow for their input, basic, and hproper languages. 4.1
Proposition 12. The class REG is characterized by basic and h-proper languages of deterministic hRLWWautomata which use only the operations MVR, CR, Restart, and which use the operation CR only when the window is at the position just to the right of the left sentinel. We denote such automata by det-Rg2.
Proof. We outline only the main ideas of the proof. First we show that any basic language and h-proper language of a det-Rg2 is regular. Let Mk be a k-det-Rg2-automaton. It is not hard to see that Mk can be simulated by a finite automaton Ak+1 with a stack of size k + 1 stored within its finite control, and therefore LC(Mk) = L(Ak+1), and LhP(Mk) = LhP(Ak+1). Since the regular languages are closed under homomorphisms, LhP(Ak+1) is a regular language, too.
On the other hand, we can see from the pumping lemma for regular languages that any regular language L ⊆ Σ∗ can be accepted by a det-Rg2-automaton with working (and input) alphabet Σ.
Remark. Since det-Rg2-automata are deterministic hRLWW-automata, we see that they are completely correctness preserving for their basic languages. 4.2
As an hRRWWC-automaton is an hRRWW-automaton
which uses only CL-operations instead of SL-operations
and CR-operations instead of SR-operations, we can prove
the following theorem in a similar way as it was done for
a stronger version of hRRWW-automata in the technical
report [
Theorem 13. CFL = LhP(det-mon-hRLWWC).
Proof. The proof is based mainly on ideas from [
If M = (Q, Σ, Γ, c, $, q0, k, δ , h) is a right-monotone
hRLWW-automaton, then its characteristic language
LC(M) is context-free [
Conversely, assume that L ⊆ Σ∗ is a context-free language. Without loss of generality we may assume that L does not contain the empty word. Thus, there exists a context-free grammar G = (N, Σ, S, P) for L which is in Greibach normal form, that is, each rule of P has the form A → aα for some string α ∈ N∗ and some letter a ∈ Σ. For the following construction we assume that the rules of G are numbered from 1 to m.
From G we construct a new grammar G0 := (N, Δ, S, P0), where Δ := { (∇i, a) | 1 ≤ i ≤ m and the i-th rule of G has the form A → aα } is a set of new terminal symbols that are in one-to-one correspondence to the rules of G, and P0 := { A → (∇i, a)α | A → aα is the i-th rule of G, 1 ≤ i ≤ m }.
Obviously, a word ω ∈ Δ∗ belongs to L(G0) if and only
if ω has the form ω = (∇i1 , a1)(∇i2 , a2) · · · (∇in , an) for
some integer n > 0, where a1, a2, . . . , an ∈ Σ, i1, i2, . . . , in ∈
{1, 2, . . . , m}, and the sequence of these indices describes
a (left-most) derivation of w := a1a2 · · · an from S in G.
Let us take h((∇i, a)) = a for all (∇i, a) ∈ Δ. Then it
follows that h(L(G0)) = L(G) = L. From ω this derivation
can be reconstructed deterministically. In fact, the
language L(G0) is deterministic context-free. Hence, there
exists a deterministic right-monotone hRRC-automaton M
for this language (see [
Remark. By means of h-lexicalized restarting automata, the above construction corresponds to the linguistic effort to obtain a set of categories (auxiliary symbols) that ensures the correctness preserving property for the respective analysis by reduction. Note that in its reductions, the automaton M0 above only uses delete operations (in a special way). This is highly reminiscent of the basic (elementary) analysis by reduction learned in (Czech) basic schools. 4.3
In this subsection we will show similar results for finite and infinite classes of basic and h-proper languages and for classes of h-syntactic analysis given by certain subclasses of hRLWW-automata. At first we introduce some useful notions.
For a (sub)class X of hRLWW-automata, by fin(i)-X we denote the subclass of X-automata which can perform at most i reductions, and by fin-X we denote the union of fin(i)-X over all natural numbers i.
By LC(M, i) we denote the subset of LC(M) containing all words accepted by at most i reductions. We take LhP(M, i) = h(LC(M, i)).
Proposition 14. Let i ≥ 0, and let M be an hRLWWautomaton. Then there is a fin(i)-hRLWW-automaton M1 such that LC(M, i) = LC(M1), and if u ⇒M1 v, then u ⇒M v. If M is deterministic, then M1 is deterministic as well. Proof. The basic idea of the construction of M1 is to add to the finite control ofM the counter of possible cycles on the starting word by M. While simulating the first cycle of M, M1 already simulates the next up to i − 1 cycles of M rejecting all words which are not acceptable with at most i cycles by M. 2
We can see that a similar proposition can also be shown for hRRWW-automata.
For a positive integer k, let the prefix de(k)- denote hRLWW-automata which delete at most k symbols in each reduction.
The next proposition lays the foundation to the desired hierarchies. In order to show the next proposition we consider the following sequence of languages for k ≥ 1: Lrgk = { (ak)i | i ≥ 1 }.
LhP((k − 1)-hRLWW) 6= 0/, for all k ≥ 2.
Proof. We outline the basic ideas only. We can construct a k-det-Rg2-automaton MRk such that LC(MRk) = LhP(MRk) = Lrgk. For MRk a window of the size k suffices, becauseMRk can first move its window to the right of the left sentinel. If it sees ak, then it performs a CR-step which deletes ak. Next, if the window contains only the right sentinel, the automaton accepts, otherwise it restarts.
From Proposition 14 we can see that there is a k-detRg2-automaton MR0k such that LC(MR0k) = LhP(MR0k) = LhP(MRk, 1).
On the other hand, there is no (k − 1)-hRLWWautomaton accepting LhP(MR0k) as its h-proper language. For a contradiction, let us suppose that LhP(M) = LMhPa(MccRep0kt)s faorwaor(dk −w 1∈)-LhCR(LMW)Ws-uacuhtotmhaattohn(wM).= Tahke∈n LhP(MRk, 1). In an accepting computation on w, automaton M must perform at least one reduction, but it can delete at most (k − 1) symbols by which it obtains a word w0 of length between 1 and k − 1, hence h(w0) 6∈ LhP(MR0k) – a contradiction to LhP(M) = LhP(MR0k). 2 Corollary 3. For all types X ∈ {det-Rg2, hRR, hRRC, hRRW, hRRWWC, hRRWW, hRL, hRLC, hRLW, hRLWWC, hRLWW}, all prefixes pr 1 ∈ {λ , f in}, all prefixes pref X ∈ {λ , mon, det, det-mon}, and all k ≥ 2, the following holds: LhP(k-pr1-prefX -X ) ⊂ LhP((k + 1)-pr1-prefX -X ) and LhP(de(k)-pr1-prefX -X ) ⊂ LhP(de(k + 1)-pr1-prefX -X ). Remark. The next theorem enables us to classify finite linguistic observations in a similar way as infinite formal languages. It refines a part of the Chomsky hierarchy and gives a useful tool for classifications of several syntactic phenomena of natural languages. In order to show the next theorem we consider the following sequences of languages for k ≥ 1: Lc fk+1 = { aibi·k | i ≥ 1 } and Lcsk+1 = { aibici·k, ai+1bici·k | i ≥ 1 }.
Theorem 16. For X = hRLWWC, and k ≥ 2 the following holds:
(1) LhP(k-det-Rg2) ⊂ LhP(k-det-mon-X ) ⊂ LhP(k-det-X ),
(2) LA(k-det-Rg2) ⊂ LA(k-det-mon-X ) ⊂ LA(k-det-X ),
(3) LhP(k-det-fin-Rg2) ⊂ LhP(k-det-fin-mon-X ) ⊂ LhP(k-det-fin-X ),
(4) LA(k-det-fin-Rg2) ⊂ LA(k-det-fin-mon-X ) ⊂ LA(k-det-fin-X ).
Proof. We outline the main ideas of the proof. For k ≥ 2 and X = hRLWWC, the following inclusions follow from definitions:
(1) LhP(k-det-Rg2) ⊆ LhP(k-det-mon-X ) ⊆ LhP(k-det-X ),
(2) LA(k-det-Rg2) ⊆ LA(k-det-mon-X ) ⊆ LA(k-det-X ),
(3) LhP(k-det-fin-Rg2) ⊆ LhP(k-det-fin-mon-X ) ⊆ LhP(k-det-fin-X ),
(4) LA(k-det-fin-Rg2) ⊆ LA(k-det-fin-mon-X ) ⊆ LA(k-det-fin-X ).
It remains to show that all these inclusions are proper. We use the sequence of context-free languages Lc fk to show the first proper inclusion in all four propositions.
For any natural number k ≥ 2, it is not hard to construct a k-det-mon-hRLC-automaton Mc fk such that LC(Mc fk) = LhP(Mc fk) = Lc fk. By applying Proposition 14 for i = k, we can construct a k-det-monfin(k)-hRLC-automaton Mc fk0 such that LC(Mc fk0) = LhP(Mc fk0) = LhP(Mc fk, k).
For a contradiction, let us suppose that there is an k-detRg2-automaton Mk such that LhP(Mk) = LhP(Mc fk, k). Let us consider the word ak+1b(k+1)(k−1) ∈ LhP(Mc fk0). As this word is longer than k, Mk must use at least one cycle to accept a word w such that h(w) = ak+1b(k+1)(k−1). Since any k-det-Rg2-automaton can delete only some of the first k symbols we have a contradiction to the complete correctness preserving property of Mk. Thus, the first inclusion is proper for all four propositions of the theorem.
Using languages Lcsk we can show the second inclusion to be proper in all four propositions. Let k ≥ 2 be an integer. It is easy to construct a k-det-hRLC-automaton Mcsk such that LC(Mcsk) = LhP(Mcsk) = Lcsk. By applying Proposition 14 for i = k, we can construct a kdet-fin(k)-hRLC-automaton Mcs0k such that LC(Mcs0k) = LhP(Mcs0k) = LhP(Mcsk, k).
In order to derive a contradiction, let us assume that there is a k-mon-det-hRLWWC-automaton Mk such that LhP(Mk) = LhP(Mcsk, k). Let us consider the word ak+1bk+1c(k+1)(k−1) ∈ LhP(Mcs0k). As this word is longer than 2k, Mk must use at least two cycles to accept a word w such that h(w) = ak+1bk+1c(k+1)(k−1). Because of the correctness preserving property Mk must reduce w into a word w1 such that h(w1) = ak+1bkck·(k−1), and then it must reduce w1 to a word w2 such that h(w2) = akbkck·(k−1). But these two reductions violate the condition of monotonicity – a contradiction to the monotonicity constraint of Mk. Hence, the second inclusion is proper in all four propositions of the theorem. 2 5
We have introduced the h-lexicalized restarting list automaton (LxRLAW), which yields a formal environment that is useful for expressing the lexicalized syntax in computational linguistics. We presented a basic variant of the Chomsky hierarchy of LxRLAW-automata, which can be interpreted as a hierarchy of classes of input, basic, and hproper languages, and a hierarchy of h-syntactic analyses as well.
In the main part of the paper we have concentrated on hlexicalized (deterministic) hRLWW-automata fulfilling the constraint of weak accepting form. We have stressed the transparency of computations of these automata for their basic and h-proper languages due to the complete correctness preserving property. We believe that the automata having the complete correctness preserving property constitute a meaningful class of automata and that they cover a significant class of languages, including the classCFL.
The newly added property of weak accepting form is particularly important for computational linguistic, since it allows to use finite observations (languages) for classifications of classes of infinite and finite languages as well, as we have shown in Section 4.3.
hRLWW-automata can be considered as a refined
analytical counterpart to generative Marcus contextual
grammars (see e.g. [
We plan in the close future to show a transfer from the complete correctness preserving monotone hRRWWautomaton to the complete correctness preserving monotone LxRLAW-automaton without any restart, which in fact works like a push-down automaton. Such an automaton computes in linear time. It is also possible to obtain similar hierarchies for this type of automata as for the hRRWW-automata from Section 4.3.
We also plan to study some relaxations of the complete correctness preserving property.