# The Lattice-Valued Turing Machines and the Lattice-Valued Type 0 Grammars

Authors: Juan Tang; Yong Fang; Jian-Gang Tang
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

Purpose. The purpose of this paper is to study a class of the natural languages called the lattice-valued phrase structure languages, which can be generated by the lattice-valued type 0 grammars and recognized by the lattice-valued Turing machines. Design/Methodology/Approach. From the characteristic of natural language, this paper puts forward a new concept of the l-valued Turing machine. It can be used to characterize recognition, natural language processing, and dynamic characteristics. Findings. The mechanisms of both the generation of grammars for the lattice-valued type 0 grammar and the dynamic transformation of the lattice-valued Turing machines were given. Originality/Value. This paper gives a new approach to study a class of natural languages by using lattice-valued logic theory.


---

## Body

## 1. Introduction

According to Chomsky’s rationalist theory, the language can be divided into types by the grammar, and then, types can be recognized and processed, respectively. The fuzziness is the typical trait of the natural languages, and then, how to recognize and deal with the fuzzy natural language is becoming the more and more important subject. From the point of the reorganization for the natural language, in 1967, Wee [1] firstly introduced the fuzzy finite automata, which generated many interesting explorations. Its important applications in learning systems, automatic control, pattern recognition and database, and so on were also studied by many researchers; the more details and the fuzzy finite automata were studied by Wee and Fu [2], Santos [3–6], Lee and Zadeh [7], Kumbhojkar and Chaudhari [8, 9], Malik et al. [10–15], and so on; the authors can also refer to [16, 17].In this paper, our main purpose is to consider a class of the natural languages which is called the lattice-valued phrase structure languages. In fact, these natural languages can be generated by the lattice-valued type 0 grammars and recognized by the lattice-valued Turing machines. Moreover, the natural languages can be described by the formation mechanism and the transferred mechanism of the grammar.This paper is organized as follows. Some basic concepts such as the complete Heyting algebra, the lattice-valued language, and the corresponding membership were recalled in Section2. In Section 3, we mainly studied the lattice-valued Turing machine and the lattice-valued recursively enumerable language. Especially, the mechanisms of both the generation of grammars for the lattice-valued type 0 grammar and the dynamic transformation of the lattice-valued Turing machines were given; we used the lattice-valued logic theory to study the class of the natural languages; it seems to be that the approach which we used is new as far as we know. Finally, we study the equivalence between the lattice-valued type 0 grammar and the lattice-valued Turing machine in Section 4.


## 2. Preliminaries

Throughout this paper, a nonempty finite setΣ is called an alphabet. The element in the alphabet is called a symbol or a letter. And, Σ
* denotes the free monoid, that is, the set of all strings with letters from Σ and the empty string, where the empty string is denoted by ϵ; moreover, the length of a string x is denoted by |
x
|, which is the number of symbols in the string; for the empty string ε, we set |
ε
|
=
0.Given an alphabetΣ. The concatenation of two strings x and y is the string which was denoted by x
y and was obtained by appending the symbols of y to the right end of x. Assume x is a string, and then x
n stands for the string obtained by repeating the string x by n times. As a special case, we can define x
0
=
ε.LetΣ
1, Σ
2 be two alphabets; the product of Σ
1 and Σ
2 is given by
(1)
Σ
1
Σ
2
=
{
a
b
∣
a
∈
Σ
1
,
b
∈
Σ
2
}
.
Define n power of an alphabet Σ by
(2)
Σ
0
=
ϵ
,
Σ
n
=
Σ
n
-
1
Σ
,
n
≥
1
.Thepositive closure of Σ is
(3)
Σ
+
=
Σ
1
∪
Σ
2
∪
Σ
3
∪
Σ
4
…
,and thestar-closure of Σ is
(4)
Σ
*
=
Σ
0
∪
Σ
+
=
Σ
0
∪
Σ
1
∪
Σ
2
∪
Σ
3
∪
Σ
4
…
.SupposeL is a complete lattice; the least element and the greatest element are 0 and 1, respectively, and also satisfy the infinite distributivity law. That is, ∀
α
∈
L, β
i
∈
L, i
∈
I, we have
(5)
α
∨
(
∧
i
∈
I
β
i
)
=
∧
i
∈
I
(
α
∨
β
i
)
,
α
∧
(
∨
i
∈
I
β
i
)
=
∨
i
∈
I
(
α
∨
β
i
)
.ThenL is called a complete Heyting algebra.LetL be a complete Heyting algebra and Σ an alphabet. We call a map φ
:
Σ
*
→
L a lattice-value language. ∀
x
∈
Σ
*, φ
(
x
) denotes the membership degree of x belonging to the lattice-valued language.Letφ, φ
1, and φ
2 be the lattice-valued languages on Σ. Then(1)
φ
1
∨
φ
2 (resp., φ
1
∧
φ
2) is a lattice-valued language on Σ via
(6)
(
φ
1
∨
φ
2
)
(
x
)
=
φ
1
(
x
)
∨
φ
2
(
x
)
(
resp
.
,
(
φ
1
∧
φ
2
)
(
x
)
=
φ
1
(
x
)
∧
φ
2
(
x
)
)
.
Generally, if φ
1
,
φ
2
,
…
,
φ
n are the lattice-valued languages on Σ, then
(7)
∨
i
=
1
n
φ
i
=
(
φ
1
∨
φ
2
∨
⋯
φ
n
-
1
)
∨
φ
n
(
resp
.
∧
i
=
1
n
φ
i
=
(
φ
1
∨
φ
2
∨
⋯
φ
n
-
1
)
∨
φ
n
)
.
(2)
φ
1
∘
φ
2 is a lattice-valued language on Σ which is defined by
(8)
φ
1
∘
φ
2
(
x
)
=
∨
{
φ
1
(
y
)
∧
φ
2
(
z
)
∣
x
=
y
z
}
.
(3)
Letθ
∈
L; then θ
φ is a lattice-valued language on Σ which is defined by
(9)
(
θ
φ
)
(
x
)
=
θ
∧
φ
(
x
)
.
(4)
φ
* is a lattice-valued language on Σ which is defined by
(10)
φ
*
(
x
)
=
{
φ
(
ϵ
)
if
x
=
ϵ
∨
{
φ
(
b
1
)
∧
φ
(
b
2
)
∧
⋯
∧
φ
(
b
n
)
iii
∣
x
=
b
1
b
2
⋯
b
n
,
i
i
i
b
i
≠
ϵ
,
∀
i
=
1,2
,
…
,
n
,
n
=
1,2
,
…
}
if
x
≠
ϵ
.
Let X be a nonempty set and L a complete Heyting algebra. The map
(11)
R
:
X
×
X
⟶
Lis called the binary lattice-valued relation onX. If R
(
x
,
y
)
=
θ, we denote it by x
R
θ
y, which can be understood as the membership degree θ of x and y satisfying the relation R.LetR, S be binary lattice-valued relations on X; the composition operation of R and S is defined by
(12)
(
R
∘
S
)
(
x
,
z
)
=
∨
y
∈
X
(
R
(
x
,
y
)
∧
S
(
y
,
z
)
)
.Consider the following:(a)
(13)
R
0
(
x
)
=
{
1
x
=
y
0
x
≠
y
;
(b)
R
⊆
S
⇔
R
(
x
,
y
)
≤
S
(
x
,
y
), ∀
(
x
,
y
)
∈
X
×
X;
(c)
(
R
∪
S
)
(
x
,
y
)
=
R
(
x
,
y
)
∨
S
(
x
,
y
)
,
(
R
∩
S
)
(
x
,
y
)
=
R
(
x
,
y
)
∧
S
(
x
,
y
);
(d)
R
n
=
R
n
-
1
∘
R, R
+
=
∪
n
=
1
∞
R
n, and R
*
=
∪
n
=
0
∞
R
n are called n power, the positive closure, and the star-closure of R, respectively.


## 3. The Lattice-Valued Turing Machine and the Lattice-Valued Recursively Enumerable Language

A lattice-valued Turing machineℳ is a 7-tuple
(14)
ℳ
=
(
Q
,
Γ
,
Σ
,
δ
,
q
0
,
B
,
F
)
,
whereQ is a finite set of states;
Γ is a finite set of tape symbol and B is a special symbol of Γ called the blank;
Σ is a subset of Γ not containing B and is called the input symbols set;
δ is a transition function, that is, a map from Q
×
Γ to Q
×
Γ
×
{
-
1
,
+
1
}
×
L;
δ
(
q
,
X
)
=
(
p
,
Y
,
+
1
,
θ
) means that ℳ reads a symbol X in the state q, the next state is p, and the read-write head moves right one unit after the symbol Y in place of X on the tape. θ represents the membership degree of Y in place of X. Similarly, δ
(
q
,
X
)
=
(
p
,
Y
,
-
1
,
θ
) means that the read-write head moves left one unit after the same process as above.
F
⊆
Q is the set of final states.The above description is the definition of a single tape lattice-valued Turing machine. For then tapes lattice-valued Turing machine, the transition function is defined as the map from Q
×
Γ
n to Q
×
Γ
n
×
{
-
1
,
+
1
}
n
×
L.We useα
1
q
α
2 to denote an instantaneous description (ID for short) of the lattice-valued Turing machine ℳ, where q
0
∈
Q is the current state of ℳ and α
1
α
2 is the string of Γ
*. When the read-write head of ℳ directs symbols right which has nonblank character, α
1
q
α
2 is the string which consists of all nonblank symbols of the leftmost position to the rightmost position of the input tape of ℳ, otherwise, α
1
q
α
2 is the string which consists of all symbols of the leftmost position of the input tape of ℳ to the tape location which is directed by the read head of ℳ, and ℳ is directing the leftmost symbol of α
2.Now, we define a binary lattice-valued relation onΓ
*
Q
Γ
* as follows.Let(15)
I
D
1
=
X
1
X
2
⋯
X
i
-
1
q
X
i
X
i
+
1
⋯
X
n
be a ID of ℳ; if δ
(
q
,
X
i
)
=
(
p
,
Y
,
+
1
,
θ
), then the next ID of ℳ is
(16)
I
D
2
=
X
1
X
2
⋯
X
i
-
1
Y
p
X
i
+
1
⋯
X
n
.The membership degree ofY replacing X
i is θ; that is,
(17)
⊢
ℳ
⁡
(
I
D
1
,
I
D
2
)
=
θ
(
or  I
D
1
⊢
ℳ
θ
I
D
2
)
.Ifδ
(
q
,
X
i
)
=
(
p
,
Y
,
+
1
,
θ
), then, if i
≠
1, the next ID of ℳ is
(18)
I
D
2
=
X
1
X
2
⋯
p
X
i
-
1
Y
X
i
+
1
⋯
X
n
;
the membership degree of Y replacing X
i is θ; that is,
(19)
⊢
(
I
D
1
,
I
D
2
)
=
θ
(
⊢
ℳ
θ
or
X
1
X
2
⋯
X
i
-
1
p
X
i
X
i
+
1
⋯
X
n
i
i
i
i
i
i
i
i
⊢
ℳ
θ
X
1
X
2
⋯
p
X
i
-
1
Y
X
i
+
1
⋯
X
n
θ
(
or
X
1
X
2
⋯
X
i
-
1
p
X
i
X
i
+
1
⋯
X
n
⊢
ℳ
θ
)
.
If i
=
1, before ℳ moves on, the read-write head has been at the far left of the input tape, then the read-write head moves left, which would make the read-write head away from the input tape, which is not allowed. In order to avoid this phenomenon, in this case, we have defined that ℳ has not the next ID.Obviously,⊢
ℳ is a binary lattice-valued relation on Γ
*
Q
Γ
*
×
Γ
*
Q
Γ
*.⊢
ℳ
n denotes n power of ⊢
ℳ; that is, ⊢
ℳ
n
=
(
⊢
ℳ
)
n; ⊢
ℳ
+ denotes the positive closure of ⊢
ℳ; that is, ⊢
ℳ
+
=
(
⊢
ℳ
)
+; ⊢
ℳ
* denotes the star-closure of ⊢
ℳ; that is, ⊢
ℳ
*
=
(
⊢
ℳ
)
*.LetI
D
1
,
I
D
2
∈
Γ
*
Q
Γ
*
×
Γ
*
Q
Γ
*. By the composition definition of the binary lattice-valued relations, it is not difficult to see the following:if⊢
ℳ
n
(
I
D
1
,
I
D
2
)
=
θ
≠
0, which represents that the membership degree I
D
1 turns to I
D
2 after n steps is θ in ℳ; if ⊢
ℳ
+
(
I
D
1
,
I
D
2
)
=
θ
≠
0, which represents that the membership degree I
D
1 changes into I
D
2 after one step at least is θ in ℳ; if ⊢
ℳ
*
(
I
D
1
,I
D
2
)
=
θ
≠
0, which represents that the membership degree I
D
1 turns into I
D
2 after several steps is θ in ℳ.Definition 1.
Letℳ
=
(
Q
,
Γ
,
Σ
,
δ
,
q
0
,
B
,
F
) be a lattice-valued Turing machine. The acceptable lattice-valued language ℳ is defined by
(20)
φ
ℳ
(
x
)
=
∨
{
⊢
*
ℳ
(
q
0
x
,
α
1
q
α
2
)
∣
q
∈
F
,
α
1
,
α
2
∈
Γ
*
}
.
The language which is accepted by the lattice-valued Turing machine is called a lattice-valued recursively enumerable language.


## 4. The Lattice-Valued Type 0 Grammar and Lattice-Valued Phrase Structure Language

Thelattice-valued grammar
𝒢 is a 4-tuple 𝒢
=
(
V
,
T
,
P
,
S
), where we have the following.V is a nonempty finite set of variables and ∀
A
∈
V
,
A is called asyntactic variable (variable for short) or a nonterminal symbol. It represents a syntactic category.T is a nonempty finite set of the terminal symbols and ∀
a
∈
T
,
a is called a terminal symbol. Since the variables in V represent the syntactic category and the characters in T are the characters that appear in the sentence of language, so we have V
∩
T
=
∅.P is a set of lattice-valued of production; that is, P is a binary lattice-valued relationship on (
P
∪
T
)
*. For α
,
β
∈
(
V
∪
T
)
* and a fixed θ
∈
L, if P
(
α
,
β
)
=
θ and θ
≠
0, then it can be denoted by α
→
θ
β which is called the production on 𝒢, and the production means that the membership degree that α is defined as β is θ. α is called the left part of α
→
θ
β, β is the right part of α
→
θ
β, and θ is the membership degree that α is defined as β. The productions are termed the definitions or the grammar rules.S
∈
V is the start symbol of the grammar 𝒢.According to Chomsky hierarchy of the grammar and the concept of the fuzzy grammar of Lee and Zadeh, the lattice-valued grammar can be divided into the following four types.Definition 2.
Let𝒢
=
(
V
,
T
,
P
,
S
) be a lattice-valued grammar. Then one has the following.(1)
𝒢 is called the lattice-valued type 0 grammar or the lattice-valued phrase structure grammar, if the production in P is without any constraint conditions. The corresponding language φ
𝒢 is called the lattice-valued type 0 language or the lattice-valued phrase structure language.
(2)
𝒢 is called the lattice-valued type 1 grammar or the lattice-valued context sensitive grammar, if, for any production α
→
θ
β
∈
P, one has |
α
|
≤
|
β
|. The corresponding language φ
𝒢 is called the lattice-valued type 1 language or the lattice-valued context sensitive language.
(3)
𝒢 is called the lattice-valued type 2 grammar or the lattice-valued context-free grammar, if, for any production α
→
θ
β
∈
P, one has |
α
|
≤
|
β
| and α
∈
V. The corresponding language φ
𝒢 is called the lattice-valued type 2 language or the lattice-valued context-free language.
(4)
𝒢 is called the lattice-valued type 3 grammars or the lattice-valued regular grammar, if, for any production α
→
θ
β
∈
P, one has
(21)
A
⟶
θ
ω
,
A
⟶
λ
ω
B
(
or
A
⟶
θ
ω
,
A
⟶
λ
B
ω
)
,where A
,
B
∈
V
,
ω
∈
T
*. The corresponding language φ
𝒢 is called the lattice-valued type 3 language or the lattice-valued regular language.Definition 3.
Let𝒢
=
(
V
,
T
,
P
,
S
) be a lattice-valued grammar. Define a binary lattice-valued relationship ⇒
𝒢 on (
V
∪
T
)
* as follows:
(22)
⟹
𝒢
(
γ
α
δ
,
γ
β
δ
)
=
P
(
α
,
β
)
,
for all γ
,
δ
∈
(
V
∘
T
)
* and α
→
θ
β
∈
P, and it can be written as γ
α
δ
⇒
θ
𝒢
γ
β
δ.
If⇒
𝒢
(
γ
α
δ
,
γ
β
δ
)
=
θ
≠
0, then we can say that the membership degree that γ
α
δ can deduce γ
β
δ in the lattice-valued grammar 𝒢 is θ, or the membership degree that γ
β
δ can be reduced into γ
α
δ in the lattice-valued grammar 𝒢 is θ.
⇒
n
𝒢 denotes the n power of ⇒
𝒢; that is, ⇒
n
𝒢
=
(
⇒
𝒢
)
n; ⇒
+
𝒢 denotes the positive closure of ⇒
𝒢; that is, ⇒
+
𝒢
=
(
⇒
𝒢
)
+; ⇒
*
𝒢 denotes the star-closure of ⇒
𝒢; that is, ⇒
*
𝒢
=
(
⇒
𝒢
)
*.
Letα
,
β
∈
(
N
∪
T
)
*; according to the composition definition of the binary lattice-valued relationship, it is not difficult to see the following.
If⇒
n
𝒢
(
α
,
β
)
=
θ
≠
0 represents the membership degree that α in 𝒢 after n steps can deduce β is θ, or the membership degree that β in 𝒢 after n steps can summarize α is θ, it also can be written as α
⇒
θ
n
𝒢
β.
If⇒
+
𝒢
(
α
,
β
)
=
θ
≠
0 represents the membership degree that α in 𝒢 after at least 1 step can deduce β is θ, or the membership degree that β in 𝒢 after at least 1 step can summarize α is θ, it also can be written as α
⇒
θ
+
𝒢
β; if ⇒
*
𝒢
(
α
,
β
)
=
θ
≠
0 represents the membership degree that α in 𝒢 after some steps can deduce β is θ, or the membership degree that β in 𝒢 after some steps can summarize α is θ, it also can be written as α
⇒
θ
*
𝒢
β.Definition 4.
Let𝒢
=
(
V
,
T
,
P
,
S
) be a lattice-valued type 0 grammar, ω
∈
T
*. Define
(23)
φ
𝒢
(
ω
)
=
(
⟹
*
𝒢
)
(
S
,
ω
)
.
φ
𝒢 is called the lattice-valued language generated by lattice-valued type 0 grammar which is termed the lattice-valued type 0 language or lattice-valued phrase structure language. One calls that two lattice-valued grammars 𝒢
1, 𝒢
2 are equivalent, if they can generate the same lattice-valued languages; that is, φ
𝒢
1
=
φ
𝒢
2.


## 5. The Equivalence between the Lattice-Valued Type 0 Grammar and the Lattice-Valued Turing Machine

Theorem 5.
Ifφ can be recognized by the lattice-valued Turing machine
(24)
ℳ
=
(
Q
,
Γ
,
Σ
,
δ
,
q
0
,
B
,
F
)
.
that is, φ
=
φ
𝒢, then there exists the lattice-valued type 0 grammar 𝒢 such that φ
=
φ
𝒢.Proof.
Suppose thatφ can be recognized by lattice-valued Turing machine
(25)
ℳ
=
(
Q
,
Γ
,
Σ
,
δ
,
q
0
,
B
,
F
)
.
Formally, we construct a lattice-valued type 0 grammar 𝒢
=
(
V
,
Σ
,
P
,
A
1
), where
(26)
V
=
(
(
Σ
∪
ϵ
)
×
Γ
)
∪
{
A
1
,
A
2
,
A
3
}
∪
Q
,
and the production in P is as follows: (1)
A
1
→
q
0
A
2, its membership degree is 1, and the following productions which are not labeled with membership degree were regarded as 1;
(2)
A
2
→
[
a
,
a
]
A
2
,
∀
a
∈
Σ;
(3)
A
2
→
A
3;
(4)
A
3
→
[
ϵ
,
B
]
A
2;
(5)
A
3
→
ϵ;
(6)
q
[
a
,
X
]
→
θ
[
a
,
Y
]
p, ∀
a
∈
Σ
∪
{
ϵ
}, ∀
q
∈
Q, ∀
X
,
Y
∈
Γ, and  δ
(
q
,
X
)
=
(
p
,
Y
,
+
1
,
θ
);
(7)
[
b
,
Z
]
q
[
a
,
X
]
→
θ
p
[
a
,
Y
], ∀
X
,
Y
,
Z
∈
Γ, ∀
a
,
b
∈
Σ
∪
{
ϵ
}, ∀
q
∈
Q, and δ
(
q
,
X
)
=
(
p
,
Y
,
-
1
,
θ
);
(8)
[
a
,
X
]
q
→
q
a
q
,
q
[
a
,
X
]
→
q
a
q, q
→
ε, ∀
a
∈
Σ
∪
{
ϵ
}, ∀
X
∈
Γ, ∀
q
∈
F.
By using rules (1) and (2), we can obtain(27)
A
1
⟹
*
𝒢
q
0
[
a
1
,
a
1
]
[
a
2
,
a
2
]
⋯
[
a
n
,
a
n
]
A
2
,
where every a
i belongs to Σ. Assume that ℳ can accept a string a
1
,
a
2
,
…
,
a
n, and then there exists m such that ℳ can use at most m units of the string input on the right. Using rules (3), (4) (m times), and (5) in order, we can obtain
(28)
A
1
⟹
*
𝒢
q
0
[
a
1
,
a
1
]
[
a
2
,
a
2
]
⋯
[
a
n
,
a
n
]
[
ϵ
,
B
]
m
.
Then we only use rules (6) and (7), until an accepting state can be generated.
By the induction on movement numbers made byℳ, we can prove that, if
(29)
q
0
a
1
a
2
⋯
a
n
⟹
*
𝒢
X
θ
1
,
X
2
⋯
X
r
-
1
q
X
r
⋯
X
s
,
then
(30)
q
0
[
a
1
,
a
1
]
[
a
2
,
a
2
]
⋯
[
a
n
,
a
n
]
[
ϵ
,
B
]
m
⇒
θ
*
𝒢
[
a
1
,
X
1
]
[
a
2
,
X
2
]
⋯
[
a
r
-
1
,
X
r
-
1
]
q
×
[
a
r
,
X
r
]
⋯
[
a
m
+
n
,
X
m
+
n
]
,
for all a
1
,
a
2
…
,
a
n
∈
Σ, a
n
-
1
=
a
n
+
2
=
a
m
+
n
=
ϵ, X
1
,
X
2
⋯
X
m
+
n
∈
Γ, and X
s
-
1
=
X
s
+
2
=
X
m
+
n
=
B.
Obviously, for the 0 movement, the inductive hypothesis holds, sincer
=
1, s
=
n.
Assume that the inductive hypothesis holds for thek
-
1 movements. Let
(31)
q
0
a
1
a
2
⋯
a
n
⇒
θ
1
n
𝒢
X
1
,
X
2
⋯
X
r
-
1
q
X
r
⋯
X
s
⊢
ℳ
θ
2
Y
1
,
Y
2
⋯
Y
t
-
1
p
Y
t
⋯
Y
u
.
By the induction hypothesis,
(32)
q
0
[
a
1
,
a
1
]
[
a
2
,
a
2
]
⋯
[
a
n
,
a
n
]
[
ϵ
,
B
]
m
⇒
θ
1
*
𝒢
[
a
1
,
X
1
]
[
a
2
,
X
2
]
⋯
[
a
r
-
1
,
X
r
-
1
]
q
×
[
a
r
,
X
r
]
⋯
[
a
m
+
n
,
X
m
+
n
]
,
where each a
iand X
i satisfy the following conditions.
Ift
=
r
+
1, then the kth movement of ℳ goes to the right, so
(33)
δ
(
q
,
X
r
)
=
(
p
,
Y
r
,
+
1
,
λ
)
,
and the membership degree θ
2
=
θ
1
∧
λ. By rule (6),
(34)
q
[
a
r
,
a
r
]
⟶
λ
[
a
r
,
Y
r
]
p
is a production of 𝒢. Therefore,
(35)
q
0
[
a
1
,
a
1
]
[
a
2
,
a
2
]
⋯
[
a
n
,
a
n
]
[
ϵ
,
B
]
m
⇒
θ
2
*
𝒢
[
a
1
,
Y
1
]
[
a
2
,
Y
2
]
⋯
[
a
t
-
1
,
Y
t
-
1
]
p
×
[
a
t
,
Y
t
]
⋯
[
a
m
+
n
,
Y
m
+
n
]
,
for i
>
u, Y
i
=
B, and the membership degree θ
2
=
θ
1
∧
λ.
Ift
=
r
-
1, then the kth movement of ℳ goes to the left, we can apply rule (7) to prove the above equation, and we can obtain for the case of r
-
1
(36)
δ
(
q
,
X
r
)
=
(
p
,
Y
r
,
-
1
,
λ
)
.
By rule (8), ifp in F, then
(37)
[
a
1
,
Y
1
]
⋯
[
a
t
-
1
,
Y
t
-
1
]
p
[
a
t
,
Y
t
]
⋯
[
a
m
+
n
,
Y
m
+
n
]
⇒
θ
*
𝒢
a
1
a
2
⋯
a
n
.
Thus(38)
φ
𝒢
(
ω
)
=
⟹
*
𝒢
(
A
1
,
ω
)
=
⊢
*
ℳ
θ
(
q
0
a
1
a
2
⋯
a
n
,
X
1
,
X
2
⋯
X
r
-
1
q
X
r
⋯
X
s
)
=
⊢
*
ℳ
θ
(
q
0
ω
,
α
1
q
α
2
)
=
∨
{
⊢
*
ℳ
(
q
0
ω
,
α
1
q
α
2
)
∣
q
∈
F
,
α
1
,
α
2
∈
Γ
*
}
=
φ
ℳ
(
ω
)
.Similarly, we have the following result.Theorem 6.
Assumeφ is a language φ
𝒢 which generated by the lattice-valued type 0 grammar 𝒢
=
(
V
,
T
,
P
,
S
), and then, φ can be recognized by the lattice-valued Turing machine ℳ
=
(
Q
,
Γ
,
Σ
,
δ
,
q
0
,
B
,
F
); that is, φ
=
φ
ℳ.



---

*Source: 291870-2014-05-08.xml*