Mathematical Problems of Computer Science 54, 69–79, 2020.

UDC 519.713, 004.43

An Approximate Method for Calculating the Distance

Between Regular Languages for Multitape Finite

Automata

Tigran A. Grigoryan

IT Educational and Research Center
Yerevan State University, Armenia

e-mail: tigran.grigoryan1995@gmail.com

Abstract

Sets of word tuples, accepted by multitape finite automata and a metric space
for languages accepted by these automata, are considered. These languages are rep-
resented using the same notation as the known notation of regular expressions for
languages accepted by one-tape automata. The only difference is the interpretation of
the ”concatenation” operation in the notation.

An algorithm is proposed for calculating the introduced distance between regular
languages accepted by multitape finite automata.

Keywords: Multitape finite automata, Regular languages, Metric space.

1. Introduction

In 1959 M. O. Rabin and D. S. Scott introduced deterministic multitape finite automata
and the problem of equivalence for these automata [1].

The equivalence problem for two-tape automata was proved to be solvable in 1973 by
M.Bird [2]. In 1991 T. Harju and J. Karhumki proved the solvability of the equivalence
problem for deterministic multitape automata without any restriction on the number of
tapes [3] via a purely algebraic technique.

Many attempts were made to consider languages accepted by multitape automata. Some
notable from our point of view attempts are briefly discussed below.

In [4], B. G. Mirkin has considered a special coding for the sets of words tuples accepted
by multitape automata. The proofs and discussions are only for the case of n = 2 and there
are no explanations/proofs on how this will extend to the case of n > 2.

Another paper [5] by P. H. Starke is dedicated to the following result: ”An n-ary re-
lation R over W(X) is representable by a finite deterministic n-tape automaton iff there
exists an admissible regular expression T such that R = V aln(T)”. In the same paper the

69



70 An Approximate Method for Calculating the Distance Between Regular Languages

author mentions that ”Unfortunately there are non-admissible regular expressions T such
that V aln(T) is representable by a deterministic automaton”.

A special coding suggested in [6] is used in this paper. This coding was also used in [7]
to define regular expressions and regular events for multitape automata. The notation of
regular expressions for one-tape automata [8] was used as a notation for languages accepted
by multitape finite automata via interpreting the ”concatenation” operation differently.

Introduction of the special binary coding for elements of a free partially commutative
semigroup mentioned above leads to the consideration of multidimensional tape cells instead
of the semigroup elements. This, in turn, gives an opportunity to compare them as integer
vectors when analyzing behaviors of two automata on a given semigroup.

A metric is introduced based on these integer vectors. The metric intends to immerse
the knowledge on coding in the notion of distance between regular expressions.

The introduced metric has some boundary cases where its value is not adequate. To
adjust such cases, a new pseudo metric is introduced as an adjuster and is combined with
the former one resulting in a more suitable metric.

A polynomial algorithm is proposed for calculating the distance between regular lan-
guages.

2. Preliminaries

Recall some definitions from [6, 9].
If X is an alphabet, then the set of all words in the alphabet X, including the empty

word, will be denoted X∗, and the set of all n-element tuples of words will be denoted Xn
∗
.

Let G be a free semigroup, generated by the set of generators Y = {y1,y2, . . . ,yn}. G is
called a free partially commutative semigroup, if it is defined by a finite set of relations R
of type yiyj = yjyi [10]. We consider semigroups with identity elements (monoids) and use
the notation G = 〈Y | R〉.

Let K : Y ∗ →{0, 1}n
∗
, n = |Y | be a homomorphism over the set Y ∗, which maps words

from Y ∗ to n-element vectors in binary alphabet {0, 1}. The homomorphism K over the set
of symbols of the set Y ∗ is defined by the equation:

K(yi) = (a1i, . . . ,ani), where aij =




1, if i = j,
e, if yiyj = yjyi,
0, if yiyj 6= yjyi.

At the same time K(e) = (e, . . . ,e).
K(yiyj), i 6= j is defined in the following way:

K(yiyj) = (a1ja1i, . . . ,anjani).

K maps the concatenation of semigroup elements a = yi1 . . .yik and b = yj1 . . .yjl in the
following way:

K(ab) = K((yi1 . . .yik )(yj1 . . .yjl )) = (a1jl . . .a1j1a1ik . . .a1i1, . . . ,anjl . . .anj1anik . . .ani1 ).

Lemma 1: [9] Let yi,yj be generators of G, yi 6= yj, g1 = yiyj, g2 = yjyi be elements of G,
obtained after applying the operation of the semigroup G to generators yi and yj. Then

g1 = g2 ⇔ K(yiyj) = K(yjyi).



T. Grigoryan 71

This statement allows to consider the homomorphism K as a mapping not only over the
Y ∗, but also over the free partially commutative semigroup G.

An equivalence relation ρ over Y ∗ is specified as follows. If w1 and w2 are words from Y
∗,

w1, w2 ∈ Y ∗, then w1ρw2 if and only if w1 and w2 are representations of the same element
in G.

The relation ρ partitions Y ∗ into disjoint classes. These classes are called classes of
commutation.

Lemma 2: [6, 11] Any free partially commutative semigroup of n generators is isomorphic
to some sub-semigroup of Cartesian product of n free semigroups with two generators.

According to Lemma 2, instead of elements of the semigroup G we can consider their
binary codings.

Any n-tuple of binary words can be considered as a tuple of integers (it will be denoted
Num(cg), where cg is the binary coded n-tuple of the semigroup element g). For that, we just
treat each non-empty binary word (components of the tuple) as the binary representation of
the integer (e.g., 010111 = 23) and use 0 for the empty word e [11].

Lemma 3: [11] Any free partially commutative semigroup of n generators is isomorphic
to some sub-semigroup of the n-dimensional space, where the semigroup operation is the
concatenation of integer tuples.

The multiplication of n-element tuples is defined as componentwise multiplication of
corresponding binary words - components of tuples. The multiplication of binary words
B1 = β11 . . .β1n1 and B2 = β21 . . .β2n2 is defined as B1B2 = β2n2 . . .β21β11 . . .β1n1, i.e., the
concatenation of new letters to the source word B1 is performed starting from the leftmost
letter and is added to the left of the word B2.

In [7], the coding with n-tuples of binary words is considered to define regular expressions
and regular events over a free partially commutative semigroup. These definitions allow to
apply the already known notation of regular expressions for the case of multitape automata,
however, the concatenation operation is interpreted differently.

Let R be a regular expression over a free partially commutative semigroup. By E(R) we
denote the regular event denoted by R.

For simplicity, we will use ”word p belongs to regular event E” to indicate that ”the
equivalence class [p] belongs to E”. Also, we will use the elements of the partially commu-
tative alphabet rather than their corresponding binary coded tuples in the notation of the
regular expressions. For instance, for Y = {y1,y2}, where y1y2 = y2y1 by writing y1y∗2 + y2
we will mean (1,e)(e, 1)∗ + (e, 1).

Next, we recall the definition of multitape finite automata (MFA).
Let Q be a finite set of states, X be an input alphabet, δ : Q×X → 2Q be the transition

function, q0 ∈ Q be the initial state and F ⊆ Q be the set of final states. Assume that X
can be divided into disjoint, ordered subsets X = X1 ∪ . . . ∪ Xn such that Xi ∩i 6=j Xj = ∅
and ∀x,x′ (x ∈ Xi,x′ ∈ Xj(i 6= j),xx′ = x′x). Each subset Xi corresponds to i-th tape.

Definition 1: [1] An n-tape automaton (MFA) is called a tuple A = (Q,T,X,δ,q0,F),
where T : Q → {1, . . . ,n} is a function associating each state from Q with a certain tape
and Q = ∪ni=1Qi, such that Qi = {q|q ∈ Q,T(q) = i} ∀i = 1, . . . ,n.



72 An Approximate Method for Calculating the Distance Between Regular Languages

Automaton is called deterministic (DMFA), if ∀q ∈ Q, ∀x ∈ X |δ(q,x)| ≤ 1. Otherwise,
it is called nondeterministic (NMFA).

An NMFA with ε transitions (NMFA-ε) is a tuple A = (Q,T,X,δ,q0,F), where δ :
Q× (X ∪{ε}) → 2Q.

A path in an automaton graph [8] from an initial state to final state is called an accepted
path. A string formed by concatenating labels of all transitions in an accepted path, is called
an accepted extended word of multitape automaton [11].

An n-tuple of words (w1,w2, . . . ,wn) ∈
∏n

i=1 X
∗
i is accepted by an MFA A if and only if

there exists an extended word w ∈ X∗ accepted by A, such that wi (i = 1, . . . ,n) is a word
obtained from w by removing all symbols of all subsets Xj, j ∈{1, . . . ,n},j 6= i.

The set of all n-tuples accepted by A is called the language of the automaton A and is
denoted by L(A). Two automata are called equivalent, if they accept the same language,
i.e., A1 ≡ A2 iff L(A1) = L(A2).

Further, in this paper, we will only consider alphabets (and/or set of generators) X
satisfying the following condition: X can be divided into disjoint, ordered subsets X =
X1 ∪ . . .∪Xn such that Xi ∩i 6=j Xj = ∅ and ∀x,x′ (x ∈ Xi,x′ ∈ Xj(i 6= j),xx′ = x′x).

3. L̃k Distance

The result of Lemma 3 brings up a natural question of whether the Euclidean metric can be
applied to regular languages over free partially commutative semigroups. Obviously, it can,
however, the adequacy of such metric is questionable. To understand the issue of such a
metric, we may look at Fig. 2 and Fig. 3 of [11]. It is clear that each time adding the same
letter to the word moves it from 2n−1 −1 diagonal to 2n −1 diagonal. For example, consider
the sequence e,y1,y

2
1,y

3
1, . . .. The coordinates for its elements are (0, 0), (1, 0), (3, 0), (7, 0), . . .

correspondingly, hence, the Euclidean distance between yn and e is 2n − 1. In this section,
we will introduce a new metric, which will transform this exponential growth of difference
to a more natural and closer to linear one.

3.1. L Distance

Let G be a free partially commutative semigroup with n generators. Recall mappings Num
and K discussed in Section 2. Let Num′ be the composition of K and Num, i.e., Num′ :=
K ◦Num : G → IRn. Num′i : G → IR, (i = 1, . . . ,n) denotes the projection of the mapping
Num′(G) on the i-th axis of IRn.

Definition 2: Let g1,g2 be words in a free partially commutative semigroup G with n gen-
erators. The logarithmic distance between g1 and g2 is denoted by L(g1,g2) and is equal
to

L(g1,g2) =

√√√√lg2 Num′1(g1) + 1
Num′1(g2) + 1

+ · · · + lg2
Num′n(g1) + 1

Num′n(g2) + 1
.

L is well-defined, as ∀i = 1, . . . ,n,∀g ∈ G Num′i(g) + 1 is a positive number.
Before continuing the investigation of this metric, let us see why it has this form. Let us

consider the same sequence e,y1,y
2
1,y

3
1, . . . with the corresponding coordinates (0, 0), (1, 0),

(3, 0), (7, 0), . . .. The function lg2
Num1(g1)+1
Num1(g2)+1

, indeed, maps their exponential difference to

a linear one. Thus, L(y1,e) = L(y
2
1,y1) = L(y

3
1,y

2
1) = . . . = 1, and generally, L(y

m
1 ,y

k
1 ) =



T. Grigoryan 73

|m−k|. Additionally, adding one in numerator and denominator prevents the values in both
of them from having the illegal value 0.

Lemma 4 below states that the defined distance is a metric on the free partially commu-
tative semigroup G.

Lemma 4: Let g1,g2 and g3 be elements of a free partially commutative semigroup G with
n generators, then

1. L(g1,g2) = 0 ⇔ g1 = g2,

2. L(g1,g2) = L(g2,g1),

3. L(g1,g3) ≤ L(g1,g2) + L(g2,g3).

Proof. Let us prove each property separately.

1. The equality L(g1,g2) = 0 takes place if and only if lg
2 Num

′
i
(g1)+1

Num′
i
(g2)+1

= 0, ∀i = 1, . . . ,n.
The later one is true if and only if Num′i(g1) = Num

′
i(g2), ∀i = 1, . . . ,n. After

combining all the i-s, we will find that L(g1,g2) = 0 ⇔ Num′(g1) = Num′(g2). From
the fact that Num′ mapping is an isomorphism follows that Num′(g1) = Num

′(g2) ⇔
g1 = g2.

2. The proof of the second property follows from

lg
Num′i(g1) + 1

Num′i(g2) + 1
= − lg

Num′i(g2) + 1

Num′i(g1) + 1
, ∀i = 1, . . . ,n,

hence,

lg2
Num′i(g1) + 1

Num′i(g2) + 1
= lg2

Num′i(g2) + 1

Num′i(g1) + 1
, ∀i = 1, . . . ,n.

After combining all i-s, we get√√√√ n∑
i=1

lg2
Num′i(g1) + 1

Num′i(g2) + 1
=

√√√√ n∑
i=1

lg2
Num′i(g2) + 1

Num′i(g1) + 1
.

3. Let us denote g1i := Num
′
i(g1) and g2i := Num

′
i(g2). We need to prove that√√√√ n∑

i=1

lg2
g1i + 1

g2i + 1
+

√√√√ n∑
i=1

lg2
g2i + 1

g3i + 1
≥

√√√√ n∑
i=1

lg2
g1i + 1

g3i + 1
. (1)

Let us square both sides of the inequality (1). We get

n∑
i=1

lg2
g1i + 1

g2i + 1
+

n∑
i=1

lg2
g2i + 1

g3i + 1
+ 2

√√√√ n∑
i=1

lg2
g1i + 1

g2i + 1

√√√√ n∑
i=1

lg2
g2i + 1

g3i + 1
≥

n∑
i=1

lg2
g1i + 1

g3i + 1
. (2)

Also, it is trivial that

n∑
i=1

lg2
g1i + 1

g3i + 1
=

n∑
i=1

(
lg
g1i + 1

g2i + 1
+ lg

g2i + 1

g3i + 1

)2
. (3)



74 An Approximate Method for Calculating the Distance Between Regular Languages

After putting the identity (3) into the inequality (2) and making some simple opera-
tions, we find that in order to prove (1) it is sufficient to show that√√√√ n∑

i=1

lg2
g1i + 1

g2i + 1

√√√√ n∑
i=1

lg2
g2i + 1

g3i + 1
≥

n∑
i=1

lg
g1i + 1

g2i + 1
lg
g2i + 1

g3i + 1
. (4)

For simplicity, let us denote ui := lg
g1i+1
g2i+1

and vi := lg
g2i+1
g3i+1

. The inequality (4) takes
the following form:√

u21 + u
2
2 + . . . + u

2
n

√
v21 + v

2
2 + . . . + v

2
n ≥ u1v1 + u2v2 + . . . + unvn. (5)

(5) is the well-known Cauchy-Schwartz inequality, hence, the third property is also
proved.

Next, we define logarithmic distance on the set of all regular events over a free partially
commutative semigroup by inducing Hausdorff metric from L [12]. This distance will be
called LH distance.

Definition 3: Let E1 and E2 be regular events over a free partially commutative semigroup.
LH distance between E1 and E2 is the quantity

LH (E1,E2) = max

{
sup
r1∈E1

inf
r2∈E2

L(r1,r2), sup
r2∈E2

inf
r1∈E1

L(r1,r2)

}
.

In Definition 3 we assume that LH can have the value ∞.
For LH metric to be well-defined, we assume that LH (∅,∅) = 0 and LH (∅,P) =

LH (P,∅) = ∞,∀P 6= ∅.
The investigation of this metric shows that in most cases the evaluated distance of the

words over a free partially commutative semigroup is adequate, however, after applying the
homomorphism K◦Num on some words of the same length they appear close to each other
on the same essential diagonal on IRn [6]. For instance, consider the words akb and bka,

where k ∈ N. The logarithmic distance of these words is
√

2 lg 2
k+1
2k

, which goes to 0 as
k →∞.

To adjust the introduced metric, we consider further a notion of a distance adjuster and
combine it with the LH distance.

3.2. Adjusted L Distance

Let Y = y1,y2, . . . ,yn be the set of generators of the free partially commutative semigroup
G. K : G → {0, 1}n

∗
is the mapping from G into the semigroup of n-element tuples of

binary words. For a word g ∈ G, the binary word of zeros and ones derived from g replacing
all occurrences of the generator yi by one and all occurrences of other generators by zero is
called the mask for occurrences of generator yi ∈ Y for the word g [9].

Let g ∈ G, by dn1 (g) we will denote the n-element vector, for which i-th element is the
number of ones in the mask for occurrences of generator yi in the word g (∀i = 1, . . . ,n).
Now, we define a distance adjuster between words in G.

Let g1,g2 ∈ G. We denote the Euclidean distance between vectors dn1 (g1) and dn1 (g2) by
D(g1,g2).



T. Grigoryan 75

It is easy to check that D is a metric on {dn1 (g) | g ∈ G}. However, it is a pseudometric
on G. Indeed, consider the free partially commutative semigroup G = 〈y1,y2〉. Let us
consider the words y1y2 and y2y1. From the definition of the function d

n
1 we have that

dn1 (y1y2) = d
n
1 (y2y1) = (1, 1). Hence, the distance D(y1y2,y2y1) equals to 0, despite the fact

that y1y2 6= y2y1. This means that the metric axiom d(x,y) = 0 ⇔ x = y does not hold.
Lemma 5 states that all pseudometric properties are satisfied.

Lemma 5: Let g1,g2 and g3 be any elements of a free partially commutative semigroup G
with n generators, then

1. D(g1,g1) = 0,

2. D(g1,g2) = D(g2,g1),

3. D(g1,g3) ≤ D(g1,g2) + D(g2,g3).

Next we combine the metric L and the pseudometric D.

Definition 4: Let g1 and g2 be words in G. The vector (L(g1,g2),D(g1,g2)) is called the
vector of adjusted logarithmic metric for the words g1 and g2.

The first component of the vector of adjusted logarithmic distance is a value expressing
the difference in patterns of the words g1 and g2. Meanwhile, the second component is the
difference in the number of occurrences for each letter of the set of generators Y .

Definition 5: Let g1,g2 ∈ G. The L2 norm of the vector of adjusted logarithmic metric for
g1 and g2 is called an adjusted logarithmic distance between the words g1 and g2 and denoted
by L̃:

L̃(g1,g2) =
√
L(g1,g2)2 + D(g1,g2)2.

Theorem 1: The distance function L̃ is a metric, in other words, let g1,g2 and g3 be the
elements of a free partially commutative semigroup G, then

1. L̃(g1,g2) = 0 ⇔ g1 = g2,

2. L̃(g1,g2) = L̃(g2,g1),

3. L̃(g1,g3) ≤ L̃(g1,g2) + L̃(g2,g3).

Proof. The proof is based on the results of Lemma 4 and Lemma 5. From these two
lemmas we have that

(a) L(g1,g2) = 0 ⇔ g1 = g2,

(b) L(g1,g2) = L(g2,g1),

(c) L(g1,g3) ≤ L(g1,g2) + L(g2,g3),

(d) D(g1,g1) = 0,

(e) D(g1,g2) = D(g2,g1),



76 An Approximate Method for Calculating the Distance Between Regular Languages

(f) D(g1,g3) ≤ D(g1,g2) + D(g2,g3).

The truthiness of the properties 2 and 3 is obvious. Indeed, L̃(g1,g2) = L̃(g2,g1) follows
directly from (b) and (e), and L̃(g1,g3) ≤ L̃(g1,g2) + L̃(g2,g3) follows directly from (c) and
(f).

Now, let us prove the property 1.
If L̃(g1,g2) = 0, then L(g1,g2) = 0. From the property (a) it follows that the latter can

hold only and only if g1 = g2. So, L̃(g1,g2) = 0 ⇒ g1 = g2.
Now, we prove the opposite. If g1 = g2, then from the properties (a) and (d) it follows

that L(g1,g2) = 0 and D(g1,g2) = 0, consequently, L̃(g1,g2) = 0.

3.3. Definition of L̃H and L̃k Distances

Once more, we use Hausdorff distance to induce the adjusted L̃H metric on the set of all
regular events over a free partially commutative semigroup.

Definition 6: Let E1 and E2 be regular events over a free partially commutative semigroup.
Adjusted LH distance between E1 and E2 is called the quantity

L̃H (E1,E2) = max

{
sup
r1∈E1

inf
r2∈E2

L̃(r1,r2), sup
r2∈E2

inf
r1∈E1

L̃(r1,r2)

}
.

We apply the following assumptions for L̃H as well: L̃H (∅,∅) = 0 and L̃H (∅,P) =
L̃H (P,∅) = ∞,∀P 6= ∅.

In Section 4 it will be shown that regular expressions over a free partially commutative
semigroup are representable as nondeterministic multitape finite automata. The equivalence
problem for the latter ones is proved to be unsolvable [1]. To be able to calculate the
distance between them, we have to be able to tell when their distance is 0, which is, as
already stated, unsolvable. Hence, the calculation of L̃H is unsolvable, so, we introduce a
new distance, which takes into account the words accepted by regular expressions, having
up to some fixed length. This new distance is an approximation of L̃H .

Denote by Wk (P) (k ∈ IN is a fixed number) the following subset of the regular event P :

Wk (P) = {p|p ∈ P, |p| ≤ k},

where |p| is the length of the word p.

Definition 7: Let E1 and E2 be regular events over a free partially commutative semigroup.
L̃k distance between E1 and E2 for a fixed k ∈ IN is called the quantity

L̃k(E1,E2) = L̃H (Wk(E1),Wk(E2)).

It is obvious that L̃k is a pseudometric.

4. An Algorithm for Calculating the L̃k Distance

Denote by L(R) the language of n-tuples of words recognized by the regular expression R.



T. Grigoryan 77

Theorem 2: (On synthesis of MFA) There exists an algorithm, which synthesizes an
NMFA-ε A from a given regular expression R over a partially commutative semigroup, such
that L(A) = L(R).

One such an algorithm for synthesizing NMFA-ε from a given regular expression might
be Thompson’s construction [13] used for synthesizing one-tape automata. Indeed, one can
easily show that this construction builds an NMFA-ε A such that L(A) = L(R).

Consider regular expressions R1 and R2 over a free partially commutative semigroup.
The following algorithm calculates the L̃k (k ∈ IN) distance between E(R1) and E(R2).

1. Construct NMFA-ε for R1 and R2 using Thompson’s construction, i.e., A1 and A2,
correspondingly.

2. Find all the extended words accepted by A1 and A2 having length less than or equal
to k, i.e., Wk(A1) and Wk(A2), correspondingly.

3. Calculate L̃H distance between the finite sets Wk(A1) and Wk(A2).

Now, we calculate the complexity of the proposed algorithm.
Let l1 and l2 be the numbers of operations (+,

∗, ·) in R1 and R2, correspondingly. The
first step of the algorithm takes O(li) time for Ri (i = 1, 2) and constructs an automaton
with at most 2li states [13].

At the second step, the complexity of the construction of set Wk(Ai) (i = 1, 2) is

O
(
(2li)

2k
)
.

At the third step, we construct the binary codings of the words, then their corresponding
integer vectors. This takes c1k time for a word having k length, where c1 is some constant.
The calculation of the distance between two integer vectors is c2m, where m is the number
of letters in the alphabet.

So, the overall complexity of the proposed algorithm can be estimated as O(km(2l1 +
2l2)

2k).

5. Conclusion

In this paper, a special binary coding of the elements in a free partially commutative semi-
group [6] has been considered. This coding is used to define regular expressions for multitape
finite automata and a distance, which is shown to be a metric. As the calculation problem
of this metric is unsolvable, in order to provide an approximate solution for this problem, a
modification of the metric was considered.

A method, having a polynomial complexity, was proposed for approximate calculation of
the distance between those regular expressions.

References

[1] M. O. Rabin and D. S. Scott, “Finite Automata and Their Decision Problems”, IBM
J. Res. Dev., vol. 3, no. 2, pp. 114–125, 1959.

[2] M. Bird, “The Equivalence Problem for Deterministic Two-Tape Automata”, J. Com-
put. Syst. Sci., vol. 7, no. 2, pp. 218–236, 1973.



78 An Approximate Method for Calculating the Distance Between Regular Languages

[3] T. Harju and J. Karhumaki, “The Equivalence Problem of Multitape Finite Au-
tomata”, Theor. Comput. Sci., vol. 78, no. 2, pp. 347-355, 1991.

[4] B. G. Mirkin, ”On the theory of multitape automata”, Cybernetics, vol. 2, no. 5, pp.
9-14, 1966. doi:10.1007/BF01073664.

[5] P. H. Starke, “On the Representability of Relations by Deterministic and Nondetermin-
istic MultiTape Automata”, International Symposium on Mathematical Foundations
of Computer Science, pp. 114-124, 1975.

[6] A. A. Letichevsky, A. S. Shoukourian and S. K. Shoukourian, “The equivalence prob-
lem of deterministic multitape finite automata: a new proof of solvability using a
multidimensional tape”, International Conference on Language and Automata Theory
and Applications, pp. 392–402, 2010.

[7] T. A. Grigoryan, “Some Results on Regular Expressions for Multitape Finite Au-
tomata”, Proceedings of the YSU: Physical and Mathematical Sciences, vol. 53, no. 2,
pp. 82-90, 2019.

[8] V. M. Glushkov, “The Abstract Theory of Automata”, Russian Mathematical Surveys,
vol. 16, no. 5, pp. 1-53, 1961.

[9] A. B. Godlevskii, A. A. Letichevskii and S. K. Shukuryan, “Reducibility of program-
scheme functional equivalence on a nondegenerate basis of rank unity to the equivalence
of automata with multidimensional tapes”, Cybernetics, vol. 16, no. 6, pp. 793-799,
1980.

[10] A. H. Clifford and G. B. Preston, The Algebraic Theory of Semigroups, Second Edition,
ser. Mathematical Surveys and Monographs, American Mathematical Society, vol. 7.1,
1961.

[11] H. A. Grigoryan and S. K. Shoukourian. ”Polynomial algorithm for equivalence prob-
lem of deterministic multitape finite automata”, Theor. Comput. Sci., vol. 833, pp.
120-132, 2020.

[12] F. Hausdorff, Set Theory, Fourth Edition, Chelsea Pub Co, 1991.

[13] A. V. Aho, R. Sethi R and J. D. Ullman, Compilers: Principles, Techniques, and Tools,
World Student Series Edition, ser. Addison-Wesley Series in Computer Science, 1986.

Submitted 09.06.2020, accepted 05.10.2020.



T. Grigoryan 7 9

´³½Ù³Å³å³í»Ý í»ñç³íáñ ³íïáÙ³ïÝ»ñÇ Ñ³Ù³ñ ϳÝáݳíáñ
É»½áõÝ»ñÇ ÙÇç¨ Ñ»é³íáñáõÃÛáõÝÁ ѳßíáÕ Ùáï³íáñ »Õ³Ý³Ï

îÇ·ñ³Ý ². ¶ñÇ·áñÛ³Ý

ºñ¨³ÝÇ å»ï³Ï³Ý ѳٳÉë³ñ³Ý

e-mail: tigran.grigoryan1995@gmail.com

²Ù÷á÷áõÙ

¸Çï³ñÏíáõÙ »Ý µ³½Ù³Å³å³í»Ý í»ñç³íáñ ³íïáÙ³ïÝ»ñÇ ÏáÕÙÇó ׳ݳãíáÕ
µ³é»ñÇ Ïáñï»ÅÝ»ñÇ µ³½ÙáõÃÛáõÝÝ»ñ ¨ ³Û¹ ³íïáÙ³ïÝ»ñÇ ÏáÕÙÇó ׳ݳãíáÕ É»½áõÝ»ñÇ
íñ³ ë³ÑÙ³Ýí³Í Ù»ïñÇÏ³Ï³Ý ï³ñ³ÍáõÃÛáõÝ: ²Ûë É»½áõÝ»ñÁ Ý»ñϳ۳óí³Í »Ý ÝáõÛÝ
·ñ»É³Ó¨áí, ÇÝã Ù»Ï Å³å³í»Ý³Ýáó ³íïáÙ³ïÝ»ñÇ ÏáÕÙÇó ׳ݳãíáÕ Ï³Ýáݳíáñ
É»½áõÝ»ñÇ Ñ³Ù³ñ ϳÝáݳíáñ ³ñï³Ñ³ÛïáõÃÛáõÝÝ»ñÁ: ØÇ³Ï ï³ñµ»ñáõÃÛáõÝÁ <<ÏáÝ-
ϳï»Ý³ódz>> ·áñÍáÕáõÃÛ³Ý Ù»Ïݳµ³ÝáõÃÛáõÝÝ ¿:

Ïðèáëèæåííûé ìåòîä âû÷èñëåíèÿ ðàññòîÿíèÿ ìåæäó
ðåãóëÿðíûìè ÿçûêàìè äëÿ ìíîãîëåíòî÷íûõ

êîíå÷íûõ àâòîìàòîâ

Òèãðàí À. Ãðèãîðÿí

Åðåâàíñêèé ãîñóäàðñòâåííûé óíèâåðñèòåò
e-mail: tigran.grigoryan1995@gmail.com

Àííîòàöèÿ

Ðàññìàòðèâàþòñÿ ðåãóëÿðíûå âûðàæåíèÿ äëÿ ìíîãîëåíòî÷íûõ êîíå÷íûõ
àâòîìàòîâ. Êàæäîå ðåãóëÿðíîå âûðàæåíèå îïèñûâàåò ÿçûê - ìíîæåñòâî
êîðòåæåé ñëîâ, ïðèíèìàåìûõ äàííûì ìíîãîëåíòî÷íûì êîíå÷íûì àâòîìàòîì.
Òàêæå ðàññìîòðåíî ìåòðè÷åñêîå ïðîñòðàíñòâî ÿçûêîâ, ïðèíèìàåìûõ ìíîãî-
ëåíòî÷íûìè êîíå÷íûìè àâòîìàòàìè. Ýòè ÿçûêè ïðåäñòàâëåíû ñ ïîìîùüþ
òîé æå íîòàöèè, êîòîðàÿ èñïîëüçóåòñÿ â ðåãóëÿðíûõ âûðàæåíèÿõ äëÿ ÿçûêîâ,
ðàñïîçíàâàåìûõ îäíîëåíòî÷íûìè àâòîìàòàìè. Åäèíñòâåííàÿ ðàçíèöà - â èíîé
èíòåðïðåòàöèè êàæäîé îïåðàöèè ”êîíêàòåíàöèÿ” íîòàöèè.

Îïðåäåëåíà ìåòðèêà è ïðåäëîæåí àëãîðèòì äëÿ âû÷èñëåíèÿ ðàññòîÿíèÿ
ìåæäó ðåãóëÿðíûìè âûðàæåíèÿìè, ïðèíèìàåìûìè ìíîãîëåíòî÷íûìè êîíå÷íûìè
àâòîìàòàìè.

Êëþ÷åâûå ñëîâà: ìíîãîëåíòî÷íûå êîíå÷íûå àâòîìàòû, ðåãóëÿðíûå âûðàæåíèÿ,
ìåòðè÷åñêîå ïðîñòðàíñòâî.

´³Ý³ÉÇ µ³é»ñ` µ³½Ù³Å³å³í»Ý í»ñç³íáñ ³íïáÙ³ïÝ»ñ, ϳÝáݳíáñ ³ñï³Ñ³Û-
ïáõÃÛáõÝÝ»ñ, Ù»ïñÇÏ³Ï³Ý ï³ñ³ÍáõÃÛáõÝ:

²é³ç³ñÏíáõÙ ¿ ³É·áñÇÃÙ, áñáí ѳßííáõÙ ¿ µ³½Ù³Å³å³í»Ý í»ñç³íáñ ³íïáÙ³ï-
Ý»ñÇ ÏáÕÙÇó ׳ݳãíáÕ Ï³Ýáݳíáñ ³ñï³Ñ³ÛïáõÃÛáõÝÝ»ñÇ ÙÇç¨ Ñ»é³íáñáõÃÛáõÝÁ` Áëï
Ý»ñÙáõÍí³Í Ù»ïñÇϳÛÇ:


	06_Tigran_Grigoryan_54_69_79 (1)
	Tigran_new