CÁC KỸ THUẬT XÂY DỰNG MÁY TURING
CÁC KỸ THUẬT XÂY DỰNG MÁY TURING
Nhóm thực hiện đề tài:
Nhóm thực hiện đề tài:


1. Đặng Ngọc Tuấn
1. Đặng Ngọc Tuấn
2. Lê Công Vượng
2. Lê Công Vượng
3. Trần Lương Vương
3. Trần Lương Vương
BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC ĐÀ NẴNG
___________ _
QUẢNG BÌNH, THÁNG 12 NĂM 2012
BẢO VỆ ĐỀ TÀI MÔN HỌC LÝ THUYẾT TÍNH TOÁN
03/23/15 01:41 PM Các kỹ thuật xây dựng máy Turing
2/35
MỞ ĐẦU
MỞ ĐẦU


Được PGS-TS Phan Huy Khánh
giao đề thực hiện đề tài : Các kỹ
Thuật Xây Dựng Máy Turing. Nhóm
xin trình bày như sau :
03/23/15 01:41 PM Các kỹ thuật xây dựng máy Turing
3/35
NỘI DUNG CHÍNH CỦA ĐỀ TÀI
NỘI DUNG CHÍNH CỦA ĐỀ TÀI


PHẦN I : CƠ SỞ LÝ THUYẾT
PHẦN I : CƠ SỞ LÝ THUYẾT

I. MÔ HÌNH MÁY TURING

II. CÁCH BIỂU DIỄN MÁY TURING

III.
CÁC KỸ THUẬT XÂY DỰNG MÁY TURING
CÁC KỸ THUẬT XÂY DỰNG MÁY TURING

PHẦN II : BÀI TẬP
PHẦN II : BÀI TẬP



I. PHÁT BIỂU BÀI TOÁN

II. YÊU CẦU THỰC HIỆN

III. PHÂN TÍCH VÀ GIẢI CÁC BÀI TOÁN
03/23/15 01:41 PM Các kỹ thuật xây dựng máy Turing
4/35
PHÂN CÔNG VÀ CÁCH THỰC HIỆN
PHÂN CÔNG VÀ CÁCH THỰC HIỆN

Tất cả các thành viên trong nhóm đều thực hiện
Tất cả các thành viên trong nhóm đều thực hiện
việc nghiên cứu lý thuyết của môn học lý thuyết

việc nghiên cứu lý thuyết của môn học lý thuyết
tính toán
tính toán
.
.

Làm việc theo cả nhóm cùng trao đổi và đưa ra
Làm việc theo cả nhóm cùng trao đổi và đưa ra
các phương án giải quyết bài toán.
các phương án giải quyết bài toán.
03/23/15 01:41 PM Các kỹ thuật xây dựng máy Turing
5/35
CƠ SỞ LÝ THUYẾT
CƠ SỞ LÝ THUYẾT
I.Mô hình máy Turing.
I.Mô hình máy Turing.

Máy Turing là mô hình toán học cho máy tính tổng
quát, là nền tảng của quá trình xử lý của máy tính hiện
đại.

Máy Turing MT gồm một bộ điều khiển với tập hữu hạn
thạng thái Q và một đầu đọc/ghi (R/W), chuyển động
trên một băng vô hạn cả về hai phía. Băng được chia
thành từng ô, mỗi ô chứa một ký hiệu thuộc một bảng
ký hiệu hữu hạn Γ, bao gồm cả ký hiệu trắng B (Blank).



Ví dụ một mô tả hoạt động của máy Turing như hình 1.



03/23/15 01:41 PM Các kỹ thuật xây dựng máy Turing
6/35
CƠ SỞ LÝ THUYẾT
CƠ SỞ LÝ THUYẾT

Hình 1.1 -
Hình 1.1 -


Mô tả một máy Turing
Mô tả một máy Turing
B a
1
a
2
a
3
a
4
a
5
… a
n
B
q
k
Đầu R/W
03/23/15 01:41 PM Các kỹ thuật xây dựng máy Turing

7/35
CƠ SỞ LÝ THUYẾT
CƠ SỞ LÝ THUYẾT
Định nghĩa
Định nghĩa
1. Máy Turing là một hệ thống gồm 7 thành phần
1. Máy Turing là một hệ thống gồm 7 thành phần
MT = (Q,
MT = (Q,
∑,
∑,
Γ
Γ
,
,
δ
δ
, q0, B, F), trong đó:
, q0, B, F), trong đó:

Q: tập khác rỗng, hữu hạn các trạng thái.
Q: tập khác rỗng, hữu hạn các trạng thái.

Γ
Γ
: tập khác rỗng, hữu hạn các ký tự được phép viết trên
: tập khác rỗng, hữu hạn các ký tự được phép viết trên
băng.
băng.


B: ký hiệu thuộc
B: ký hiệu thuộc
Γ
Γ
, ký hiệu trắng (Blank) trên băng.
, ký hiệu trắng (Blank) trên băng.

∑
∑
: tập các ký tự đầu vào và là tập con của
: tập các ký tự đầu vào và là tập con của
Γ
Γ
, B
, B
∉
∉


Γ
Γ
.
.

δ
δ
: hàm chuyển: Q
: hàm chuyển: Q
×
×



Γ
Γ


→
→
Q
Q
×
×


Γ
Γ


×
×
{L, R,
{L, R,
∅
∅
}
}

q
q
0

0


∈
∈
Q là trạng thái bắt đầu
Q là trạng thái bắt đầu

F
F
⊆
⊆
Q là tập các trạng thái kết thúc.
Q là tập các trạng thái kết thúc.
03/23/15 01:41 PM Các kỹ thuật xây dựng máy Turing
8/35
CƠ SỞ LÝ THUYẾT
CƠ SỞ LÝ THUYẾT
II.BIỂU DIỄN MÁY TURING
II.BIỂU DIỄN MÁY TURING
.
.

Máy Turing có thể
Máy Turing có thể được mô tả theo ba cách:

Các mô tả hiện trạng

Bảng chuyển trạng


Biểu đồ (đồ thị) chuyển trạng.
03/23/15 01:41 PM Các kỹ thuật xây dựng máy Turing
9/35
CƠ SỞ LÝ THUYẾT
CƠ SỞ LÝ THUYẾT
III.
III.


CÁC KỸ THUẬT XÂY DỰNG MÁY TURING
CÁC KỸ THUẬT XÂY DỰNG MÁY TURING

Mục tiêu của mục này là nhằm đưa ra khả năng phán
Mục tiêu của mục này là nhằm đưa ra khả năng phán
đoán làm thế nào mà một máy Turing có thể được dùng
đoán làm thế nào mà một máy Turing có thể được dùng
để tính toán theo một cách thức không giống như loại máy
để tính toán theo một cách thức không giống như loại máy
tính thông thường.
tính thông thường.

Máy Turing đúng ra có sức mạnh như một máy tính thông
Máy Turing đúng ra có sức mạnh như một máy tính thông
thường.
thường.



Đặc biệt là chúng ta sẽ học đựợc máy Turing có thể thực
Đặc biệt là chúng ta sẽ học đựợc máy Turing có thể thực

hiện phân loại các sự tính toán dựa trên những máy
hiện phân loại các sự tính toán dựa trên những máy
Turing khác
Turing khác

Khả năng xem xét cả hai loại máy Turing và các chương
Khả năng xem xét cả hai loại máy Turing và các chương
trình máy tính khác là những gì chúng ta có thể chứng
trình máy tính khác là những gì chúng ta có thể chứng
minh cho các bài toán không thể giải quyết được.
minh cho các bài toán không thể giải quyết được.
03/23/15 01:41 PM Các kỹ thuật xây dựng máy Turing
10/35
CƠ SỞ LÝ THUYẾT
CƠ SỞ LÝ THUYẾT
Để xây dựng một máy Turing ta có thể thực hiện theo sự
Để xây dựng một máy Turing ta có thể thực hiện theo sự
hướng dẫn dưới đây:
hướng dẫn dưới đây:
–
Mục tiêu của việc đọc ký hiệu của đầu R/W là
Mục tiêu của việc đọc ký hiệu của đầu R/W là
cần biết xem “cái gì” máy Turing cần thực hiện ở
cần biết xem “cái gì” máy Turing cần thực hiện ở
bước tiếp theo. Máy phải ghi lại những ký hiệu
bước tiếp theo. Máy phải ghi lại những ký hiệu
đã đọc qua.
đã đọc qua.
–
Số các trạng thái phải là cực tiểu. Điều này thực

Số các trạng thái phải là cực tiểu. Điều này thực
hiện được bằng cách chỉ thay đổi trạng thái khi
hiện được bằng cách chỉ thay đổi trạng thái khi
có sự thay đổi ký tự cần ghi vào băng hoặc khi
có sự thay đổi ký tự cần ghi vào băng hoặc khi
có sự thay đổi hướng chuyển dịch của đầu R/W.
có sự thay đổi hướng chuyển dịch của đầu R/W.
03/23/15 01:41 PM Các kỹ thuật xây dựng máy Turing
11/35
CƠ SỞ LÝ THUYẾT
CƠ SỞ LÝ THUYẾT
III.1. Lưu trữ trong bộ điều khiển (Storage in the
III.1. Lưu trữ trong bộ điều khiển (Storage in the
finite control)
finite control)

Đối với TM cơ sở bộ điều khiển lưu trữ một trạng
Đối với TM cơ sở bộ điều khiển lưu trữ một trạng
thái
thái

Kỹ thuật lưu trữ trong bộ điều khiển là có thể lưu
Kỹ thuật lưu trữ trong bộ điều khiển là có thể lưu
trữ một lượng thông tin hữu hạn. Gồm k thành
trữ một lượng thông tin hữu hạn. Gồm k thành
phần trong đó:
phần trong đó:


+ Thành phần lưu giữ điều khiển

+ Thành phần lưu giữ điều khiển
+ k-1 thành phần còn lại lưu giữ trạng thái
+ k-1 thành phần còn lại lưu giữ trạng thái
03/23/15 01:41 PM Các kỹ thuật xây dựng máy Turing
12/35
CƠ SỞ LÝ THUYẾT
CƠ SỞ LÝ THUYẾT
Một máy Turing được xem như có bộ điều khiển cho
phép lưu trữ nhiều trạng thái trên đầu đọc và nhiều
rãnh trên băng.
03/23/15 01:41 PM Các kỹ thuật xây dựng máy Turing
13/35
CƠ SỞ LÝ THUYẾT
CƠ SỞ LÝ THUYẾT
Ví dụ
Ví dụ
: Xét máy Turing M nhận vào ký hiệu đầu tiên trên
: Xét máy Turing M nhận vào ký hiệu đầu tiên trên
chuỗi nhập (viết trên bộ chữ cái {0, 1}), lưu trữ vào bộ điều
chuỗi nhập (viết trên bộ chữ cái {0, 1}), lưu trữ vào bộ điều
khiển và kiểm tra rằng ký hiệu này không có xuất hiện ở vị
khiển và kiểm tra rằng ký hiệu này không có xuất hiện ở vị
trí nào khác trên chuỗi nữa hay không ?Chúng ta sẽ thiết
trí nào khác trên chuỗi nữa hay không ?Chúng ta sẽ thiết
kế một máy Turing
kế một máy Turing


Ta xây dựng TM M (Q, {0, 1}, {0, 1, B},
Ta xây dựng TM M (Q, {0, 1}, {0, 1, B},

δ
δ
, [q
, [q
0
0
, B], B, F})
, B], B, F})
với
với


hàm chuyển
hàm chuyển
δ
δ
như sau:
như sau:
1)
1)
δ
δ
([q
([q
0
0
, B], 0) = ([q
, B], 0) = ([q
1
1

, 0], 0, R)
, 0], 0, R)


δ
δ
([q
([q
0
0
, B], 1) = ([q
, B], 1) = ([q
1
1
, 1], 1, R)
, 1], 1, R)
Bắt đầu từ trạng thái [q
Bắt đầu từ trạng thái [q
0
0
, B], TM đọc và lưu trữ ký hiệu đầu
, B], TM đọc và lưu trữ ký hiệu đầu
tiên trên băng vào thành phần thứ hai trong bộ điều khiển.
tiên trên băng vào thành phần thứ hai trong bộ điều khiển.
03/23/15 01:41 PM Các kỹ thuật xây dựng máy Turing
14/35
CƠ SỞ LÝ THUYẾT
CƠ SỞ LÝ THUYẾT
2)
2)

δ
δ
([q
([q
1
1
, 0], 1) = ([q
, 0], 1) = ([q
1
1
, 0], 1, R)
, 0], 1, R)


δ
δ
([q
([q
1
1
, 1], 0) = ([q
, 1], 0) = ([q
1
1
, 1], 0, R)
, 1], 0, R)
Nếu các ký hiệu được đọc tiếp theo không giống
Nếu các ký hiệu được đọc tiếp theo không giống
với ký hiệu đang lưu trữ thì tiếp tục di chuyển
với ký hiệu đang lưu trữ thì tiếp tục di chuyển

sang phải.
sang phải.
3)
3)
δ
δ
([q
([q
1
1
, 0], B) = ([q
, 0], B) = ([q
1
1
, B], 0,
, B], 0,
∅
∅
)
)


δ
δ
([q
([q
1
1
, 1], B) = ([q
, 1], B) = ([q

1
1
, B], 0,
, B], 0,
∅
∅
)
)


M đi vào trạng thái kết thúc [q
M đi vào trạng thái kết thúc [q
1
1
, B] khi gặp Blank.
, B] khi gặp Blank.




03/23/15 01:41 PM Các kỹ thuật xây dựng máy Turing
15/35
CƠ SỞ LÝ THUYẾT
CƠ SỞ LÝ THUYẾT
III.2. Nhiều rãnh trên băng (Multiple tracks)
III.2. Nhiều rãnh trên băng (Multiple tracks)

Với kỹ thuật này băng của TM được chia thành k
Với kỹ thuật này băng của TM được chia thành k
thành phần, với k > 1 và hữu hạn. Một ký hiệu

thành phần, với k > 1 và hữu hạn. Một ký hiệu
trên băng được xét là một bộ gồm k ký hiệu, mỗi
trên băng được xét là một bộ gồm k ký hiệu, mỗi
ký hiệu nằm trên một rãnh.
ký hiệu nằm trên một rãnh.

Ví dụ
Ví dụ
: Thiết kế TM nhận vào một số nguyên n
: Thiết kế TM nhận vào một số nguyên n
(viết ở dạng nhị phân) và kiểm tra xem đó có phải
(viết ở dạng nhị phân) và kiểm tra xem đó có phải
là số nguyên tố hay không ?
là số nguyên tố hay không ?
03/23/15 01:41 PM Các kỹ thuật xây dựng máy Turing
16/35
CƠ SỞ LÝ THUYẾT
CƠ SỞ LÝ THUYẾT
TM với băng 3 rãnh
Mô tả một TM với k = 3, kiểm tra số n = 47 viết trên
rãnh 1 dưới dạng nhị phân, TM đang thực hiện phép chia
47 cho 5. Nó đã trừ 2 lần số 5 vào số 47, vậy ở rãnh 3
hiện đang có số 37.
03/23/15 01:41 PM Các kỹ thuật xây dựng máy Turing
17/35
CƠ SỞ LÝ THUYẾT
CƠ SỞ LÝ THUYẾT


III.3. Đánh dấu ký hiệu (Checking off symbols)

III.3. Đánh dấu ký hiệu (Checking off symbols)

Kỹ thuật đánh dấu thường dùng để nhận diện các ngôn
Kỹ thuật đánh dấu thường dùng để nhận diện các ngôn
ngữ được định nghĩa bằng cách lặp lại chuỗi chẳng hạn
ngữ được định nghĩa bằng cách lặp lại chuỗi chẳng hạn
như {ww
như {ww
|
|
w
w
∈
∈


∑
∑
*}; {wcy
*}; {wcy
|
|
w, y
w, y
∈
∈


∑
∑

*, w
*, w
≠
≠
y} hoặc {ww
y} hoặc {ww
R
R


|
|
w
w
∈
∈


∑
∑
*} hoặc các ngôn ngữ có độ dài các chuỗi con cần
*} hoặc các ngôn ngữ có độ dài các chuỗi con cần
được so sánh, như {aibi
được so sánh, như {aibi
|
|
i
i
≥
≥

1} hoặc {aibjck
1} hoặc {aibjck
|
|
i = j hoặc j =
i = j hoặc j =
k}.
k}.

Ta dùng một rãnh mở rộng trên băng để giữ ký hiệu
Ta dùng một rãnh mở rộng trên băng để giữ ký hiệu
đánh dấu
đánh dấu
√
√
. Ký hiệu
. Ký hiệu
√
√
xuất hiện khi ký hiệu trên rãnh
xuất hiện khi ký hiệu trên rãnh
ngay bên dưới nó đã hoặc đang được xét bởi TM.
ngay bên dưới nó đã hoặc đang được xét bởi TM.
03/23/15 01:41 PM Các kỹ thuật xây dựng máy Turing
18/35
CƠ SỞ LÝ THUYẾT
CƠ SỞ LÝ THUYẾT
III.4. Chương trình con (Subroutines)
III.4. Chương trình con (Subroutines)


Cũng giống như một chương trình máy tính hiện đại, máy Turing có
Cũng giống như một chương trình máy tính hiện đại, máy Turing có
thể đóng vai trò tương tự như bất kỳ một kiểu chương trình con nào
thể đóng vai trò tương tự như bất kỳ một kiểu chương trình con nào
trong ngôn ngữ lập trình bao gồm thủ tục đệ qui hoặc có tham số.
trong ngôn ngữ lập trình bao gồm thủ tục đệ qui hoặc có tham số.

Ý tưởng chung là ta viết một phần chương trình của TM như là một
Ý tưởng chung là ta viết một phần chương trình của TM như là một
chương trình con. Nó sẽ được thiết kế có chứa một trạng thái khởi
chương trình con. Nó sẽ được thiết kế có chứa một trạng thái khởi
đầu và một trạng thái trở về, trạng thái trở về là trạng thái không có
đầu và một trạng thái trở về, trạng thái trở về là trạng thái không có
phép chuyển kế tiếp và nó sẽ đóng vai trò là trạng thái khởi đầu của
phép chuyển kế tiếp và nó sẽ đóng vai trò là trạng thái khởi đầu của
một TM khác hoặc là một trạng thái nào đó trong một TM khác. Nghĩa
một TM khác hoặc là một trạng thái nào đó trong một TM khác. Nghĩa
là từ trạng thái trở về của TM này ta tiếp tục các phép chuyển của một
là từ trạng thái trở về của TM này ta tiếp tục các phép chuyển của một
TM khác, sự kiện này có ý nghĩa như là gọi một chương trình con
TM khác, sự kiện này có ý nghĩa như là gọi một chương trình con
khác hoặc tiếp tục thực hiện chương trình cấp trên.
khác hoặc tiếp tục thực hiện chương trình cấp trên.

Lưu ý, các trạng thái của chương trình con phải phân biệt với chương
Lưu ý, các trạng thái của chương trình con phải phân biệt với chương
trình cấp trên của nó.
trình cấp trên của nó.
03/23/15 01:41 PM Các kỹ thuật xây dựng máy Turing
19/35

PHẦN II : BÀI TẬP
PHẦN II : BÀI TẬP
03/23/15 01:41 PM Các kỹ thuật xây dựng máy Turing
20/35
BÀI TẬP
BÀI TẬP
Bài tập 8.3.1
Bài tập 8.3.1
. Thiết kế lại máy Turing trong bài tập
. Thiết kế lại máy Turing trong bài tập
8.2.2 để nắm những ưu điểm của các kỹ thuật xây
8.2.2 để nắm những ưu điểm của các kỹ thuật xây
dựng TM đã được thảo luận trong phần 8.3.
dựng TM đã được thảo luận trong phần 8.3.
a. Thiết lập máy Turing đón nhận chuỗi w. Với w là
a. Thiết lập máy Turing đón nhận chuỗi w. Với w là
chuỗi với các ký tự 0 và 1 sao cho số ký tự 0 và số
chuỗi với các ký tự 0 và 1 sao cho số ký tự 0 và số
ký tự 1 có trong chuỗi luôn luôn bằng nhau.
ký tự 1 có trong chuỗi luôn luôn bằng nhau.
b. Thiết lập máy Turing đón nhận chuỗi { a
b. Thiết lập máy Turing đón nhận chuỗi { a
n
n
b
b
n
n
c
c

n
n
│n
│n
≥1}
≥1}
c. {WW
c. {WW
R
R
│w là chuỗi bất kỳ của 0 và 1}
│w là chuỗi bất kỳ của 0 và 1}
03/23/15 01:41 PM Các kỹ thuật xây dựng máy Turing
21/35
BÀI TẬP
BÀI TẬP
Bài tập 8.3.2
Bài tập 8.3.2
. Một thao
. Một thao
t
t
ác chung trong kỹ thuật xây dựng
ác chung trong kỹ thuật xây dựng
máy Turing cần phải "Dịch qua" (Shifting over). Một cách lý
máy Turing cần phải "Dịch qua" (Shifting over). Một cách lý
tưởng chúng ta tạo ra một ô phụ ở vị trí đầu từ hiện tại, ở
tưởng chúng ta tạo ra một ô phụ ở vị trí đầu từ hiện tại, ở
đó chúng ta có thể chứa nhiều ký tự hơn. Tuy nhiên chúng
đó chúng ta có thể chứa nhiều ký tự hơn. Tuy nhiên chúng

ta không thể soạn thảo trên băng từ theo phương pháp
ta không thể soạn thảo trên băng từ theo phương pháp
này. Hơn nữa, chúng ta phải di chuyển nội dung của ô đến
này. Hơn nữa, chúng ta phải di chuyển nội dung của ô đến
bên phải của vị trí đầu từ đang đứng hiện tại vào một ô bên
bên phải của vị trí đầu từ đang đứng hiện tại vào một ô bên
phải và rồi tìm chúng theo cách lui lại từ vị trí hiện tại của
phải và rồi tìm chúng theo cách lui lại từ vị trí hiện tại của
đầu đọc, cách trình bày với hệ thống này định nghĩa : cho
đầu đọc, cách trình bày với hệ thống này định nghĩa : cho
phép dùng một ký tự đặc biệt để đánh dấu vị trí mà đầu từ
phép dùng một ký tự đặc biệt để đánh dấu vị trí mà đầu từ
phải quay trở lại.
phải quay trở lại.
03/23/15 01:41 PM Các kỹ thuật xây dựng máy Turing
22/35
Bài tập 8.3.1
Bài tập 8.3.1
Câu a
Câu a
:
:
Thiết lập máy Turing đón nhận chuỗi w. Với w là chuỗi với các ký
Thiết lập máy Turing đón nhận chuỗi w. Với w là chuỗi với các ký
tự 0 và 1 sao cho số ký tự 0 và số ký tự 1 có trong chuỗi luôn luôn
tự 0 và 1 sao cho số ký tự 0 và số ký tự 1 có trong chuỗi luôn luôn
bằng nhau.
bằng nhau.
03/23/15 01:41 PM Các kỹ thuật xây dựng máy Turing
23/35

Bài tập 8.3.1
Bài tập 8.3.1

Cải tiến kỹ thuật xây dựng máy Turing dùng kỹ thuật
Cải tiến kỹ thuật xây dựng máy Turing dùng kỹ thuật
lưu trữ trong bộ điều khiển và đánh dấu ký hiệu
lưu trữ trong bộ điều khiển và đánh dấu ký hiệu
Với d = 0 hoặc 1; e = 0 hoặc 1, ta định nghĩa hàm chuyển
Với d = 0 hoặc 1; e = 0 hoặc 1, ta định nghĩa hàm chuyển
δ
δ
như sau:
như sau:
1)
1)
δ
δ
([q1, B], [B, d]) = ([q2, d], [
([q1, B], [B, d]) = ([q2, d], [
√
√
, d], R)
, d], R)
2)
2)
δ
δ
([q2, d], [B, d]) = ([q2, d], [B, d], R)
([q2, d], [B, d]) = ([q2, d], [B, d], R)
3)

3)
δ
δ
([q2, d], [
([q2, d], [
√
√
, e]) = ([q2, d], [
, e]) = ([q2, d], [
√
√
, e], R)
, e], R)
4)
4)
δ
δ
([q2, d], [B, d’]) = ([q3, B], [
([q2, d], [B, d’]) = ([q3, B], [
√
√
, d’], L)
, d’], L)
5)
5)
δ
δ
([q3, B], [
([q3, B], [
√

√
, e]) = ([q3, B], [
, e]) = ([q3, B], [
√
√
, e], L)
, e], L)
6)
6)
δ
δ
([ q3, B], [B, d]) = ([q3, B], [B, d], L)
([ q3, B], [B, d]) = ([q3, B], [B, d], L)
7)
7)
δ
δ
([ q3, B], [B, B]) = ([q3, B], [B, B], R)
([ q3, B], [B, B]) = ([q3, B], [B, B], R)
8)
8)
δ
δ
([q3, B], [
([q3, B], [
√
√
, d]) = ([q2, d], [
, d]) = ([q2, d], [
√

√
, d], R)
, d], R)
03/23/15 01:41 PM Các kỹ thuật xây dựng máy Turing
24/35
Bài tập 8.3.1
Bài tập 8.3.1
Câu b :
Câu b :
Thiết kế MT đoán nhận ngôn ngữ L = { a
Thiết kế MT đoán nhận ngôn ngữ L = { a
n
n
b
b
n
n
c
c
n
n


|
|
n
n
≥
≥
1}.

1}.
Biểu diễn MT dưới dạng cơ bản :
Biểu diễn MT dưới dạng cơ bản :
03/23/15 01:41 PM Các kỹ thuật xây dựng máy Turing
25/35
Bài tập 8.3.1
Bài tập 8.3.1

Chuổi abc :
Chuổi abc :
q
q
0
0
abc xq⊢
abc xq⊢
1
1
bc xyq⊢
bc xyq⊢
2
2
c xq⊢
c xq⊢
3
3
yz q⊢
yz q⊢
3
3

xyz xq⊢
xyz xq⊢
0
0
yz
yz
xyq⊢
xyq⊢
4
4
z xyzq⊢
z xyzq⊢
5
5
B xyzBq⊢
B xyzBq⊢
6
6
B
B

Chuổi a
Chuổi a
2
2
b
b
2
2
c

c
2:
2:
q
q
0
0
a
a
2
2
b
b
2
2
c
c
2
2
xaq⊢
xaq⊢
1
1
b
b
2
2
c
c
2

2
xayq⊢
xayq⊢
2
2
bc
bc
2
2
xaybq⊢
xaybq⊢
2
2
c
c
2
2
xayq⊢
xayq⊢
3
3
bzc
bzc
xaq⊢
xaq⊢
3
3
ybzc xq⊢
ybzc xq⊢
3

3
aybzc q⊢
aybzc q⊢
3
3
xaybzc xq⊢
xaybzc xq⊢
0
0
aybzc
aybzc
xxq⊢
xxq⊢
1
1
ybzc xxyyq⊢
ybzc xxyyq⊢
2
2
zc xxyyq⊢
zc xxyyq⊢
3
3
zz
zz
xq⊢
xq⊢
3
3
xyyzz xxq⊢

xyyzz xxq⊢
0
0
yyzz xxyyq⊢
yyzz xxyyq⊢
4
4
zz xxyyzzq⊢
zz xxyyzzq⊢
5
5
B
B
xxyyzzBq⊢
xxyyzzBq⊢
6
6
B
B