Partial actions and automata
We use the notion of a partial action of a monoid to introduce a generalization of automata, which we call ``a preautomaton''. We study properties of preautomata and of languages recognized by preautomata.
Gespeichert in:
| Datum: | 2011 |
|---|---|
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут прикладної математики і механіки НАН України
2011
|
| Schriftenreihe: | Algebra and Discrete Mathematics |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/154801 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Partial actions and automata / M. Dokuchaev, B. Novikov, G. Zholtkevych // Algebra and Discrete Mathematics. — 2011. — Vol. 11, № 2. — С. 51–63. — Бібліогр.: 7 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-154801 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-1548012025-02-09T10:07:23Z Partial actions and automata Dokuchaev, M. Novikov, B. Zholtkevych, G. We use the notion of a partial action of a monoid to introduce a generalization of automata, which we call ``a preautomaton''. We study properties of preautomata and of languages recognized by preautomata. This paper was partially supported by CNPq and FAPESP (Brazil). 2011 Article Partial actions and automata / M. Dokuchaev, B. Novikov, G. Zholtkevych // Algebra and Discrete Mathematics. — 2011. — Vol. 11, № 2. — С. 51–63. — Бібліогр.: 7 назв. — англ. 1726-3255 2000 Mathematics Subject Classification:20M30, 20M35, 68Q70 https://nasplib.isofts.kiev.ua/handle/123456789/154801 en Algebra and Discrete Mathematics application/pdf Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
We use the notion of a partial action of a monoid to introduce a generalization of automata, which we call ``a preautomaton''. We study properties of preautomata and of languages recognized by preautomata. |
| format |
Article |
| author |
Dokuchaev, M. Novikov, B. Zholtkevych, G. |
| spellingShingle |
Dokuchaev, M. Novikov, B. Zholtkevych, G. Partial actions and automata Algebra and Discrete Mathematics |
| author_facet |
Dokuchaev, M. Novikov, B. Zholtkevych, G. |
| author_sort |
Dokuchaev, M. |
| title |
Partial actions and automata |
| title_short |
Partial actions and automata |
| title_full |
Partial actions and automata |
| title_fullStr |
Partial actions and automata |
| title_full_unstemmed |
Partial actions and automata |
| title_sort |
partial actions and automata |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2011 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/154801 |
| citation_txt |
Partial actions and automata / M. Dokuchaev, B. Novikov, G. Zholtkevych // Algebra and Discrete Mathematics. — 2011. — Vol. 11, № 2. — С. 51–63. — Бібліогр.: 7 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT dokuchaevm partialactionsandautomata AT novikovb partialactionsandautomata AT zholtkevychg partialactionsandautomata |
| first_indexed |
2025-11-25T16:07:04Z |
| last_indexed |
2025-11-25T16:07:04Z |
| _version_ |
1849779106931015680 |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 11 (2011). Number 2. pp. 51 – 63
c© Journal “Algebra and Discrete Mathematics”
Partial actions and automata
M. Dokuchaev, B. Novikov, G. Zholtkevych
Abstract. We use the notion of a partial action of a monoid
to introduce a generalization of automata, which we call “a preau-
tomaton”. We study properties of preautomata and of languages
recognized by preautomata.
Introduction
The concept of the partial action has been introduced in [2] for groups
and extended to monoids in [7]. Therefore it is natural to investigate the
influence in Automata Theory of the replacement of the full action of a
free monoid by a partial action. Our article is devoted to the study of this
topic.
We propose the term “preaction” for a notion which is called “partial
action” in [7] and “strong partial action” in [4]. A generalization of the
notion of an automaton which appears here, will be called “a preautomaton”.
This change of the terminology is caused by the fact that the term “partial
automaton” is widely used in Automata Theory in a different sense (see,
e.g., [3]).
We shall use the following facts from Automata Theory:
the Kleene theorem on regular languages,
the Myhill–Nerode theorem on languages and congruences,
the Eilenberg theorem on prefix decomposition.
All of them can be found in [1, 3, 5] etc.
This paper was partially supported by CNPq and FAPESP (Brazil).
2000 Mathematics Subject Classification: 20M30, 20M35, 68Q70.
Key words and phrases: Partial action, monoid, automaton, recognizable lan-
guage, prefix code.
52 Partial actions and automata
The paper begins with a preliminary section on preactions. Then we
define a preautomaton (Section 2) and describe its globalization. These
notions are illustrated by an example in Section 3. Next we pass to
languages which are recognized by preautomata. The Eilenberg theorem is
generalized and examples are given which show that the Kleene theorem
does not hold for preautomata (Section 6). In the last section we compare
the preautomata with other classes of machines.
We use the notation ϕ : A 99K B for a partial mapping from A to
B (unlike to a full mapping A → B). If ϕ(a) is not defined for a ∈ A
we write ϕ(a) = ∅. The free semigroup on the alphabet Σ is denoted by
Σ+, the free monoid on Σ by Σ∗ and its identity element by ε. We use
right preactions, as it is customary in Automata Theory to deal with right
actions.
1. Preactions
We shall need some known information about partial actions (preactions)
of monoids which we recall in this section.
Definition 1. [7] Let M be a monoid with the identity e, X a set. A
preaction M on X is a partial mapping X × M 99K X : (x, a) 7→ xa,
such that
∀x ∈ X xe = x,
∀a, b ∈ M ∀x ∈ X xa 6= ∅ & (xa)b 6= ∅ =⇒ x(ab) 6= ∅ & (xa)b = x(ab),
∀a, b ∈ M ∀x ∈ X xa 6= ∅ & x(ab) 6= ∅ =⇒ (xa)b 6= ∅ & (xa)b = x(ab).
The preactions of the given monoid M form a category PAM : its
objects are sets with preactions given on them, and morphisms are such
mappings ϕ : X → Y that
∀a ∈ M ∀x ∈ X xa 6= ∅ =⇒ ϕ(x)a 6= ∅ & ϕ(xa) = ϕ(x)a.
Preactions appear in the following situation. Suppose that a full action
of a monoid M is given on a set Y and X ⊂ Y . Then the restriction of
the action to X is a preaction.
Conversely, let X ×M 99K X be a preaction and Y ⊃ X.
Definition 2. A full action Y ×M → Y is called a globalization if its
restriction on X coincides with the given preaction.
The following construction gives a globalization for any preaction
X ×M 99K X. Define on the set X ×M a relation ⊢:
(x, ab) ⊢ (xa, b) ⇐⇒ xa 6= ∅.
M. Dokuchaev, B. Novikov, G. Zholtkevych 53
Let ≃ is the equivalence generated by ⊢ and Y = (X×M)/ ≃. Denote
by [x, a] the ≃-class containing the pair (x, a). Set [x, a]b = [x, ab] for
[x, a] ∈ Y, b ∈ M . This defines a full action on Y .
Theorem 1. [7] The above defined action Y ×M → Y is a globalization
of the preaction X ×M 99K X; the mapping α : X → Y : x 7→ [x, e] is an
injective morphism, and any morphism of the preaction M on X in a full
action of M can be factored through α.
2. Preautomata
We will use the definition of an automaton in the following form (in this
section the condition of finiteness is ignored):
Definition 3. Let X be a set and Σ∗ the free monoid over an alphabet
Σ. An automaton is a triple (Σ, X, δ∗) where δ∗ : X × Σ∗ → X is a
mapping such that
∀x ∈ X δ∗(x, ε) = x, (1)
∀u, v ∈ Σ∗ ∀x ∈ X δ∗(x, uv) = δ∗(δ∗(x, u, ), v). (2)
The main object of this article is a more general concept:
Definition 4. A preautomaton is such a triple (Σ, X, δ∗), where δ∗ :
X × Σ∗
99K X is a partial mapping, that
a) the above condition (1) is satisfied;
b) if δ∗(x, u) 6= ∅ and δ∗(δ∗(x, u), v) 6= ∅, then δ∗(x, uv) 6= ∅ and
δ∗(x, uv) = δ∗(δ∗(x, u), v); (3)
c) if δ∗(x, u) 6= ∅ and δ∗(x, uv) 6= ∅, then δ∗(δ∗(x, u), v) 6= ∅ and also
the equation (3) is fulfilled.
Clearly, preautomata correspond to preactions of the free monoid Σ∗.
It will be convenient to omit the symbol δ∗, i. e. to write xu instead of
δ∗(x, u), and denote the preautomaton by (Σ, X).
Theorem 1 enables us to associate to the preautomaton M = (Σ, X) an
automaton Mgl = (Σ, Y ), where Y = (X × Σ∗)/ ≃ is the set constructed
in Section 1. We call Mgl a globalization of M.
Using the fact that the monoid Σ∗ is free, the description of ≃ can be
simplified:
54 Partial actions and automata
Theorem 2. Define the following relation ≈ on the set X × Σ∗:
(x, a) ≈ (y, b) ⇐⇒ ∃ a′, b′, p ∈ Σ∗ : a = a′p, b = b′p, xa′ = yb′ 6= ∅.
Then ≈ coincides with ≃.
Proof. If (x, a) ≈ (y, b) then (x, a′p) ⊢ (xa′, p) = (yb′, p) and (y, b′p) ⊢
(yb′, p), whence ≈⊆≃. Let us prove the converse inclusion.
Obviously, ≈ is reflexive and symmetric. Let us check its transitivity.
Let (x, a) ≈ (y, b) ≈ (z, d), a = a′p, b = b′p = c′q, d = d′q and
xa′ = yb′ 6= ∅, yc′ = zd′ 6= ∅. Since Σ∗ is free, either p divides q or vice
versa. Let, say, p = uq. Then c′ = b′u.
Since yb′ 6= ∅, y(b′u) 6= ∅ then (xa′)u = (yb′)u = y(b′u) 6= ∅. Hence
(xa′)u = x(a′u), as xa′ 6= ∅. On the other hand a′p = (a′u)q, and we obtain
(x, a′p) = (x, (a′u)q) ≈ (z, d′q), since (xa′)u = (yb′)u = y(b′u) = yc′ = zd′.
Thus, ≈ is an equivalence, and ≈⊃≃ as clearly ≈⊃⊢.
Corollary 1. Every ≃-class can be uniquely written either in the form
[x,w], where x ∈ X, w = a1 . . . an ∈ Σ∗ and x(a1 . . . ai) = ∅ for any
i, 1 ≤ i ≤ n, or in the form [x, ε] (n = 0).
Theorems 1 and 2 allow to give the following interpretation of a finite
preautomaton. Suppose that a system with a possibly infinite set of states
is given, and only a finite subset of its states is accessible to our observation.
Then the preautomaton, obtained by restriction of the system to the set
of observable states, can be considered as a model of the observable part
of the system.
3. Example
Consider the infinite automaton N = (Σ,Z) for which Σ = {a, b} is a
two-lettered alphabet, Z is the set of integers and the transition function
is defined by the equalities n · a = n+1, n · b = n− 1. Observe that this is
the natural action of Σ∗ on its factor-monoid by the congruence generated
by the relation ab = ε, and this factor-monoid is isomorphic to the infinite
cyclic group. Set X = {0, 1} ⊂ Z. Then the restriction of the action of
Σ∗ on X gives a preautomaton M = (Σ, X). In order to describe the
corresponding preaction, we denote the length of a word w by |w|, the
number of entries of the letter a in w by |w|a, and set ‖w‖ = |w|a − |w|b.
Then
0 · w =
0 if ‖w‖ = 0,
1 if ‖w‖ = 1,
∅ otherwise,
1 · w =
0 if ‖w‖ = −1,
1 if ‖w‖ = 0,
∅ otherwise.
M. Dokuchaev, B. Novikov, G. Zholtkevych 55
Corollary 1 allows to describe the globalization Mgl = (Σ, Y ). A word
w = aα1bβ1 . . . aαnbβn will be called 1-simple if ‖aα1bβ1 . . . aαibβi‖ > 0 for
all i ≥ 1 (this implies, in particular, that α1 > 0). The word ε will be
considered 1-simple too. Similarly, a word w = bβ1aα1 . . . bβnaαn (and also
the word ε) is 0-simple if ‖bβ1aα1 . . . bβiaαi‖ < 0 for all i ≥ 1. It is easy
to see that every ≃-class has form [0, w] or [1, w], where the word w is
0-simple or 1-simple, respectively.
Note that the preautomaton M = (Σ, X) cannot be considered as
a restriction of a finite automaton. Indeed, let P = (Σ,W ) be such an
automaton with a transition function δ : W × Σ → W and X ⊂ W .
Since W is finite, δ(0, bk) = δ(0, bm) for some distinct k,m. Suppose
k < m. As ‖bkak‖ = 0 then δ(δ(0, bk), ak) = δ(0, bkak) = 0 · (bkak) = 0.
Further, δ(0, bmak) = δ(δ(0, bm), ak) = δ(δ(0, bk), ak) = 0, and since our
preautomaton is a restriction of P, then 0 · (bmak) = 0. This contradicts
the inequality ‖bmak‖ < 0.
In addition, it is possible to obtain from Theorem 2 the description
of the semigroup of Mgl = (Σ, Y ). We recall that the semigroup of an
automaton is the factor-monoid obtained from Σ∗ by identification of the
words equally acting of the states.
Proposition 1. The semigroup of Mgl = (Σ, Y ) coincides with Σ∗ =
{a, b}∗.
Proof. Suppose that the words u, v ∈ Σ∗, u 6= v, act equally on all states of
Mgl = (Σ, Y ). In particular, [0, bβ ]u = [0, bβ ]v for all β > 0. As bβu = bβv,
then by Theorem 2 u = u′w, v = v′w and 0 · bβu′ = 0 · bβv′ 6= ∅. Hence,
‖u′‖ = ‖v′‖ =
{
β
β + 1
≥ β.
But ‖u′‖ = |u′|a − |u′|b ≤ |u′| ≤ |u| is a bounded quantity in contrary
with arbitrariness of β.
Remark. It is easy to see that the semigroup of the original automaton
N = (Σ, Z) is isomorphic to Z.
4. Recognizability
In what follows we will consider only finite preautomata, i. e. preautomata
M = (Σ, X) such that |X| < ∞. A preautomaton M = (Σ, X), in which
an initial state x0 ∈ X and a terminal subset T ⊂ X are chosen, will
be called a preacceptor and denoted by M = (Σ, X, x0, T ).
56 Partial actions and automata
As well as in the classical situation, we call a language L ⊂ Σ∗
recognizable if there is a preacceptor M = (Σ, X, x0, T ) for which
L = {w ∈ Σ∗ | ∅ 6= x0w ∈ T}.
In what follows recognizability will be understood in this sense.
The following assertion generalizes the Myhill–Nerode theorem and
gives an algebraic characterization of recognizable languages:
Theorem 3. A language L ⊂ Σ∗ is recognized by a preacceptor if and only
if L is the union of a finite number of classes of some right congruence
on Σ∗.
Proof. Suppose that L is recognized by a (finite) preacceptor M =
(Σ, X, x0, T ). Consider its globalization Mgl = (Σ, Y ). It follows from
Corollary 1 that L is recognized by the acceptor
N = (Σ, [x0, ε]Σ
∗, [x0, ε], [T, ε])
where [T, ε] = {[t, ε] | t ∈ T}, [x0, ε]Σ
∗ ⊆ Y. The relation
ρ = {(u, v) ∈ Σ∗ × Σ∗ | [x0, ε]u = [x0, ε]v}
is a right congruence, L is a union of ρ-classes and the number of these
classes does not exceed |[T, ε]| = |T | < ∞.
Conversely, let ρ be a right congruence on Σ∗ and L be the union of a
finite number (say, n) of ρ-classes C1, . . . , Cn.
In the (infinite) automaton K = (Σ,Σ∗/ρ) we choose the ρ-class E
containing ε as the initial state, and T = {C1, . . . , Cn} ⊂ Σ∗/ρ as the
terminal subset. Then (Σ, T ∪ {E}, E, T ) is a finite preacceptor which is
a restriction of K and recognizes L.
Corollary 2. Given languages L,M ⊂ Σ∗ which are recognized by preac-
ceptors, then L ∩M is also recognizable.
Proof. Let L and M are finite unions of classes of right congruences λ
and µ respectively. Then L ∩M is a union of a finite number of classes of
the congruence λ ∩ µ.
Corollary 3. For the single-letter alphabet Σ = {a} a language L ⊂ Σ∗ is
recognizable by a preacceptor exactly when L is recognizable by an acceptor.
Proof. The semigroup Σ+ = {a}+ is the unique infinite monogenic semi-
group up to isomorphism [6]. As it is commutative, all its right congruences
are two-sided ones. Factor-semigroups by these congruences (except the
M. Dokuchaev, B. Novikov, G. Zholtkevych 57
trivial one) are finite. Therefore if a language L is recognized by a preac-
ceptor, but not by an acceptor, it should be a union of a finite number of
classes of the trivial congruence, i. e. L is a finite subset in Σ+, hence L is
regular.
Example 1. The language L = {anbn | n > 0} over the alphabet
Σ = {a, b} is a class of the right syntactic congruence [6]. Therefore it is
recognized by a preacceptor. As it is well-known [6], L is not recognized
by any finite acceptor.
Example 2. For an arbitrary finite Σ each ideal of the monoid Σ∗ is
recognizable, since it is an element of the Rees factor-semigroup.
5. Minimization of a preacceptor
The study of recognizability of languages by preacceptors leads to the
notion of the syntactic equivalence of preacceptors.
Definition 5. Preacceptors M1 and M2 over the same alphabet Σ are
called syntactically equivalent if they recognize the same language.
As in the theory of acceptors, a question arises how to find in a class
of syntactically equivalent preacceptors a preacceptor whose set of states
has minimal cardinality. The first step is given by the following lemma.
Lemma 1. Let M = (Σ, X, x0, T ) be a preacceptor, Y = {x0} ∪ T ,
M0 = (Σ, Y, x0, T ) the restriction of M on Y . Then M0 is syntactically
equivalent to M.
Proof. is obvious.
Thanks to Lemma 1, in the study of language recognition by preaccep-
tors we can restrict the set of states including only the initial and terminal
states.
We recall from [6] that the right syntactic congruence on Σ∗ of a
language L ⊂ Σ∗ is the relation ≡L defined by
w1 ≡L w2 ⇐⇒ ∀u ∈ Σ∗ (w1u ∈ L ⇔ w2u ∈ L)
The language L is the union of some classes of this relation; moreover,
any right congruence, such that L is a union of its classes, is contained in
≡L. This property allows us to reformulate Theorem 3 as follows:
Lemma 2. A language L ⊂ Σ∗ is recognized by a (finite) preacceptor if
and only if it is the union of a finite number of classes of its right syntactic
congruence.
58 Partial actions and automata
We will denote the ≡L-class containing u ∈ Σ∗ by [u]≡L
. Fix a set of
representatives u1, . . . , uk ∈ L of the ≡L-classes of L.
For the set X≡L
= {[ε]≡L
, [u1]≡L
, . . . , [uk]≡L
} ⊂ Σ∗/ ≡L we define the
partially defined map δ∗ : X≡L
× Σ∗
99K X≡L
as follows:
∀ [u]≡L
∈ X≡L
δ∗([u]≡L
, ε) = [u]≡L
, (4)
∀ [u]≡L
∈ X≡L
∀w ∈ Σ+ uw /∈ L ⇒ δ∗([u]≡L
, w) = ∅, (5)
∀ [u]≡L
∈ X≡L
∀w ∈ Σ+ uw ∈ L ⇒ δ∗([u]≡L
, w) = [uw]≡L
. (6)
Theorem 4. Let L ⊂ Σ∗ is a finite union of ≡L-classes. Then the
preacceptor
M≡L
= (Σ, X≡L
, [ε]≡L
, {[u]≡L
| u ∈ L})
with the partial mapping δ∗, defined by (4)–(6), recognizes L.
Moreover, M≡L
has the minimal set of states among all finite preac-
ceptors recognizing L.
Proof. First of all we check that δ∗ defines a preaction. Indeed, condition
a) of Definition 4 is fulfilled by virtue of (4), and conditions b) and c)
follow from (5) and (6). Thus, M≡L
is a preacceptor which recognizes L.
Now, let M = (Σ, X, x0, T ) be a preacceptor recognizing L. Define a
mapping f : X≡L
→ X by the formulas
f([ε]≡L
) = x0,
f([ui]≡L
) = x0 · ui, i = 1, . . . , k.
As ui ∈ L, x0 · ui ∈ T .
We wish to show that f is injective. Assume that x0 · ui = x0 · uj
for some 1 ≤ i 6= j ≤ k. Suppose that uiw ∈ L, so ∅ 6= x0 · (uiw) ∈ T .
Since ui ∈ L, then ∅ 6= (x0 · ui) · w = x0 · (uiw) ∈ T by the definition of a
preautomaton. The assumption x0 · ui = x0 · uj implies ∅ 6= x0 · (ujw) =
(x0 ·uj) ·w ∈ T , i. e. ujw ∈ L. Thus uiw ∈ L yields ujw ∈ L, and similarly
ujw ∈ L =⇒ uiw ∈ L. Hence ui ≡L uj , contradicting i 6= j. Thus f is
injective and |X≡L
| ≤ |X|.
6. Prefix decomposition
In this section Theorem VI.4.1 from [1] is generalized to finite preautomata.
Lemma 3. Suppose that L is a language over an alphabet Σ which is
recognized by a preacceptor M = (Σ, X, x0, T ) and let Ly (y ∈ T ) be
languages such that Ly is recognized by a preacceptor My = (Σ, X, x0, Ty =
{y}). Then L =
∐
y∈T
Ly (disjoint union).
M. Dokuchaev, B. Novikov, G. Zholtkevych 59
Proof. w ∈ L if and only if x0w = y for some y ∈ T , i. e. w ∈ Ly.
We remind that a (possibly, empty) language L ⊂ Σ∗ is called a prefix
code [6] if u, uv ∈ L implies v = ε. The language {ε} is also considered as
a prefix code (note that if a prefix code contains ε then it is equal {ε}). It
is well-known and easily verified that the monoid S = L∗, generated by a
prefix code L, is free. Such a monoid is called unitary and is characterized
by the property:
u, uv ∈ S =⇒ v ∈ S. (7)
The following lemma generalizes (7):
Lemma 4. Let H and C be prefix codes over an alphabet Σ. Then
u, uv ∈ HC∗ =⇒ v ∈ C∗.
Proof. Suppose that
u = hc1 . . . cm, uv = h′c′1 . . . c
′
n (h, h′ ∈ H, ci, c
′
j ∈ C).
Then hc1 . . . cmv = h′c′1 . . . c
′
n. Since H is a prefix code, then h = h′, and
hence c1 . . . cmv = c′1 . . . c
′
n. This implies ci = c′i (1 ≤ i ≤ m ≤ n) and
v = c′m+1 . . . c
′
n ∈ C∗.
It is interesting to note that the property of prefix codes to generate
free monoids can be generalized as follows:
Proposition 2. 1 Let P1, . . . , Pn (n ≥ 1) be prefix codes over Σ and
w ∈ P1 · . . . · Pn. Then the decomposition w = w1 . . . wn, where wi ∈ Pi
for i = 1, . . . , n, is unique.
Proof. We use induction on n. For n = 1 the statement is evident. Suppose
that it is true for k < n. Let w = w′
1 . . . w
′
n = w′′
1 . . . w
′′
n be two representa-
tions of a word w ∈ P1 · . . . ·Pn where w′
i, w
′′
i ∈ Pi for i = 1, . . . , n. Denote
u′ = w′
2 . . . w
′
n, u′′ = w′′
2 . . . w
′′
n and assume that |u′| 6= |u′′|, for example,
|u′| < |u′′|. Then |w′
1| > |w′′
1 |, so w′′
1 is a prefix of w′
1, which is impossible
for a prefix code.
Hence, |u′| = |u′′|. Then u′ = u′′ as suffixes of w of the same length,
and w′
1 = w′′
1 as prefixes. By induction the equality u′ = u′′ implies
w′
2 = w′′
2 , . . . , w
′
n = w′′
n.
Definition 6. A language L ∈ Σ∗, such that L = HC∗ where H and C
are prefix codes over Σ, will be called a p-language.
1Proposition 2 will not be used in this article.
60 Partial actions and automata
Remark. Notice that if H = ∅ then HC∗ = ∅.
Theorem 5. A language L over an alphabet Σ is recognized by some
preacceptor M = (Σ, X, x0, {y}) with a single terminal state if and only
if L is a p-language.
Proof. Let L be a p-language. We consider the possible cases.
1) L1 = ∅. Then L1 is recognized by the preacceptor
M = (Σ, {x0, y}, {x0}, {y})
where the action is trivial:
x0w = x0, yw = y.
2) L2 = C∗. Then L2 is recognized by the preacceptor
M = (Σ, {x0}, {x0}, {x0})
where preaction It is given by formulas:
x0w =
{
x0 if w ∈ C∗,
∅ if w /∈ C∗.
The fact that the above is a preaction, is verified using (7).
3) L3 = HC∗ with H 6= {ε}. Then L3 is recognized by the preacceptor
M = (Σ, {x0, y}, {x0}, {y}) with the preaction:
x0w =
y, if w ∈ HC∗,
x0, if w = ε,
∅, if w 6∈ HC∗ ∪ {ε},
yw =
{
y if w ∈ C∗,
∅ if w 6∈ C∗.
We need to show that the above formulas define a preautomaton. For
the action of an input word on the state y the fulfilment of the conditions
of Definition 4 follows from (7). As to the action on x0, the condition b) of
Definition 4 is immediate, and in order to see c) suppose that x0u 6= ∅ and
x0(uv) 6= ∅. If u = ε, the condition c) is obvious. Otherwise u, uv ∈ HC∗
and by Lemma 4, v ∈ C∗.
Now we prove that if a language L is recognized by a preacceptor of
the form M = (Σ, X, x0, {y}) then it is a p-language. For every word
w ∈ Σ∗ denote by Px(w) the set of all proper prefixes of w. For K ⊂ Σ∗
write Px(K) = {Px(w) | w ∈ K}. Set
H = {w ∈ Σ∗ | x0w = y & ∀u ∈ Px(w) x0u 6= y}.
M. Dokuchaev, B. Novikov, G. Zholtkevych 61
and similarly,
C = {w ∈ Σ∗ | yw = y & ∀u ∈ Px(w) yu 6= y}.
By construction H and C are prefix codes and, moreover, L ⊃ HC∗ since
x0w = y for any word w ∈ HC∗. It remains to show that L ⊂ HC∗.
Let w ∈ L, i. e. x0w = y. First assume that x0 = y. Write w = uv,
where u is the least prefix of w for which x0u = x0 (and therefore,
u ∈ H = C). By definition of a preaction ∅ 6= (x0u)v = x0w, whence
x0v = x0, and consequently v ∈ C∗. Thus we obtain w = uv ∈ HC∗ = C∗.
If x0 6= y, then write w = uv, where u is the prefix of the least length,
such that x0u = y. It follows that u ∈ H and yv = y. As above, v ∈ C∗,
whence w ∈ HC∗.
Theorem 5 allows us to transfer to preautomata the concept of a prefix
decomposition ([1], Theorem VI.4.1):
Corollary 4. If a language L over the alphabet Σ is recognized by some
preacceptor then L decomposes into a disjoint union
L =
∐
i
HiC
∗
i ,
where Hi, Ci are prefix codes over Σ.
Proof. The corollary follows from Theorem 5 and Lemma 3.
The converse statement does not hold:
Example 3. It is directly seen that the language H1 = {a}+ is recognized
(even by a finite acceptor), and the language H2 = {anbn | n ≥ 1} is a
prefix code. Take C1 = C2 = {ε}. The union H = H1∪H2 = H1C
∗
1∪H2C
∗
2
is not recognized by any preacceptor. Indeed, let ≡H be the right syntactic
congruence of H, and take x ∈ Σ∗. Since
anx ∈ H ⇐⇒ x = bn or x ∈ H1 ∪ {ε},
the words an form one-element ≡H -classes, and by Theorem 3 the language
H is non-recognizable.
The given example shows also that the set of languages, recognized
by finite preacceptors, is not union-closed. Moreover, it is not closed with
respect to the other Kleene’s operations, i.e. the product and the iteration:
62 Partial actions and automata
Example 4. Let H1 and H2 be the same as in Example 3. By Theorem 5
the language H∗
2 is recognizable. Consider the product K = H∗
2H1. Then
an ∈ K for n > 0 and
{x ∈ Σ∗ | anx ∈ K} ∩ {b}+ = {bn}.
Therefore all words of the form an are pairwise non-equivalent with respect
to the right congruence ≡K . As in Example 3, it follows that K is non-
recognized.
Example 5. The language L = H2 ∪ {a} is recognized by a preacceptor,
since it consists of two ≡L-classes H2 and {a}. Consider the iteration
M = L∗. It is easy to see that ambn ∈ M iff m ≥ n. Hence,
{x ∈ Σ∗ | amx ∈ M} ∩ {b}+ = {bk | k ≤ m}.
As above, the words am are pairwise non-equivalent with respect to ≡M .
Therefore, M = L∗ is not recognized by any preacceptor.
Conclusion
The obtained results allow to clarify relations between the class of finite
preautomata FPA and other types of machines.
Obviously, FPA includes the class of finite automata FA. This inclusion
is strict since the language from Example 1 is not recognized by any
finite automaton. On the other hand, it is known [6, § 9.1] that the prefix
language {anbncn | n ≥ 1} is not context-free. According to Theorem 5
it means that FPA is not contained in the class of automata with stack
memory FSA.
At the same time, FPA does not include the class of Turing machines
TM. Indeed, the language {an
2
| n ≥ 1} is not recognized by a finite
automaton [5, ex. 4.1.2], and by Corollary 3 it is not recognized also by a
preautomaton.
On the other hand, the cardinal of the class of all prefix codes over
some finite alphabet equals to the cardinal of continuum, whereas the class
of a recursively enumerable languages over a finite alphabet is countable.
It follows that TM does not contain FPA.
References
[1] S. Eilenberg, Automata, Languages, and Machines, vol. B., Academic Press, 1976.
[2] R. Exel, Partial actions of groups and actions of semigroups, Proc. Amer. Math.
Soc., 126(1998), pp.3481-3494.
[3] W.M. L. Holcombe, Algebraic Automata Theory, Cambridge Univ. Press, 1982.
M. Dokuchaev, B. Novikov, G. Zholtkevych 63
[4] C. Hollings, Partial actions of monoids, Semigroup Forum, 75(2007), pp.293-316.
[5] J. E. Hopcroft, R. Motwani, J. D. Ullman, Introduction to Automata Theory, Lan-
guages and Computation, 2nd edition, Addison Wesley, 2001.
[6] G. Lallement, Semigroups and Combinatorial Applications, Pure and Applied
Mathematics Series, Wiley, New York, 1979.
[7] M. Megrelishvili, L. Schröder, Globalization of confluent partial actions on topolog-
ical and metric spaces, Topology and its Appl., 145(2004), pp.119-145.
Contact information
M. Dokuchaev Instituto de Matemática e Estat́ıstica Universi-
dade de São Paulo, Rua do Matão, 1010, CEP
05508-090, São Paulo, SP, Brazil
E-Mail: dokucha@ime.usp.br
B. Novikov Kharkov National University, Svobody sq., 4,
61077, Kharkov, Ukraine
E-Mail: novikov@univer.kharkov.ua
G. Zholtkevych Kharkov National University, Svobody sq., 4,
61077, Kharkov, Ukraine
E-Mail: g.zholtkevych@gmail.com
Received by the editors: 13.04.2011
and in final form 05.05.2011.
|