0.6 Máy turing  (Page 15/15)

Có thể chứng minh bằng quy nạp theo số bước dẫn xuất rằng nếu luật sinh (4) chưa được dùng đến thì chuỗi trong dẫn xuất có một trong ba dạng như sau :

1. S
2. AaiCajB, với i + 2j là một lũy thừa dương của 2.
3. AaiDajB, với i + j là một lũy thừa dương của 2.

Khi luật sinh (4) được áp dụng thì ta sẽ có chuỗi dạng AaiE, trong đó i là một lũy thừa dương của 2. Sau đó, ta chỉ có thể áp dụng i lần luật sinh (7) để đi tới dạng câu AEai. Cuối cùng, với luật sinh (8), ta thu được chuỗi dạng ai với i là lũy thừa dương của 2.

Phần tiếp theo dưới đây, chúng ta sẽ xét mối tương quan giữa văn phạm không hạn chế này và mô hình máy Turing. Chúng ta chứng minh hai Định lý dưới đây thể hiện mối tương quan giữa lớp văn phạm không hạn chế và lớp ngôn ngữ đệ quy liệt kê r.e – lớp ngôn ngữ được chấp nhận bởi một máy Turing. Định lý đầu tiên sẽ chứng tỏ rằng mọi ngôn ngữ kiểu 0 phát sinh một tập r.e. Và sau đó ta sẽ xây dựng một giải thuật để liệt kê tất cả các chuỗi thuộc văn phạm kiểu 0.

ĐỊNH LÝ 7.9 : Nếu L là L(G) với một văn phạm không hạn chế G(V, T, P, S) thì L là ngôn ngữ đệ quy liệt kê.

Chứng minh

Thiết lập một máy Turing M không đơn định, hai băng chấp nhận ngôn ngữ L. Băng thứ nhất (băng 1) của TM chứa chuỗi nhập w, còn băng thứ hai (băng 2), máy phát sinh các dạng chuỗi  của G. Đầu tiên, chuỗi  được phát sinh trên băng 2 là ký hiệu bắt đầu S. Sau đó, TM lặp lại quá trình sau :

(i) Chọn một cách ngẫu nhiên một vị trí i trên  với 1  i    , nghĩa là TM xuất phát từ bên trái chuỗi  rồi tùy chọn giữa hai khả năng : hoặc chọn i là vị trí hiện tại, hoặc dịch chuyển sang phải và lặp lại quá trình.

(ii) Chọn một luật sinh    trong số các luật sinh thuộc tập luật sinh của G.

(iii) Nếu chuỗi con  xuất hiện trong  kể từ vị trí thứ i, TM thay thế chuỗi  bởi  (dĩ nhiên nếu        thì phải dịch chuyển phần cuối của  để đủ chỗ trống cần cho phép thay thế)

(iv) So sánh chuỗi phát sinh được với chuỗi nhập w trên băng 1. Nếu giống nhau thì chuỗi mới phát sinh sẽ được chấp nhận. Nếu khác nhau thì TM trở về bước (i). Ta có thể chứng minh được rằng tất cả và chỉ có những chuỗi thuộc G mới xuất hiện trên băng 2 ở bước (iv).

Vậy L(M) = L(G) = L.

ĐỊNH LÝ 7.10 : Nếu L là ngôn ngữ đệ quy liệt kê thì L = L(G) với một văn phạm không hạn chế G nào đó.

Chứng minh

Giả sử ngôn ngữ L được chấp nhận bởi máy Turing M (Q, å, , , q0, B, F). Ta sẽ xây dựng một văn phạm không hạn chế G mà mỗi chuỗi dẫn xuất của nó phát sinh theo ba bước như sau :

(i) G phát sinh một cách ngẫu nhiên một chuỗi w thuộc . Chuỗi này được viết thành hai bản : một sẽ lưu giữ cho đến khi kết thúc, một sẽ thay đổi trong quá trình làm việc của TM.

(ii) G mô phỏng lại quá trình làm việc của của TM trên chuỗi w, bằng cách lặp lại đúng quá trình làm việc của TM.

(iii) Khi bước (ii) kết thúc, với sự xuất hiện của một trạng thái kết thúc q  F của TM (nghĩa là chuỗi w đã được TM chấp nhận). Lúc đó G tiếp tục thu giảm để chuyển dạng câu đã có về như chuỗi w. Và như vậy, có nghĩa là chuỗi w đã được G sinh ra.

Một cách hình thức, ta thiết lập văn phạm G (V, , P, S1)

Với V = ( (  {  })  )  { S1, S2, # })

Và tập luật sinh P được xây dựng như sau :

1. a) S1  #q0 S2#

b) S2  [a, a] S2#, a  

c) S2  

- Nếu (q, X) = (p, Y, R) với p, q  ; X, Y   thì thêm các luật sinh dạng (2a) và (2b) sau đây vào tập luật sinh P :

2. a) q[a, X][b, Z] [a, Y]p[b, Z], a, b    {} và Z  

b) q[a, X]#  [a, Y]p[, B], a    {}

- Nếu (q, X) = (p, Y, L) với p, q  ; X, Y   thì thêm các luật sinh dạng (2c) sau đây vào tập luật sinh P :

c) [b, Z]q[a, X] q[b, Z]p[a, Y], a, b    {} và Z  

- Nếu q  F thì thêm các luật sinh (3a-e) sau đây vào tập luật sinh P:

3. a) [a, X]q  qap, a    {} và X  

b) q[a, X]  qap, a    {} và X  

c) q#  

d) #q  

e) q  

Dùng các luật sinh (1a-c), ta có chuỗi dẫn xuất :

S1  G* #q0 [a1, a1][a2, a2]… [an, an]#

Chuỗi dẫn xuất này thể hiện hình thái bắt đầu của TM là : #q0a1a2 … an#. Bắt đầu từ bước này các quy tắc (2a-c) được áp dụng. Lưu ý rằng các luật sinh này trong G phản ánh các quy tắc chuyển trạng thái đã được thiết kế cho TM. Cho nên quá trình dẫn xuất lại trong G sẽ mô phỏng lại các bước chuyển hình thái trong quá trình làm việc của TM. Nếu quá trình đó chuyển đến một trong những trạng thái kết thúc q  F, tương ứng với trường hợp TM chấp nhận chuỗi a1a2 … an, thì trong văn phạm G các quy tắc (3a-e) sẽ được áp dụng tiếp theo và cho phép G dẫn xuất ra chính chuỗi nhập a1a2 … an. Hay ta có : S G* a1a2 … an

Phần chứng minh L(M)  L(G) và L(G)  L(M) xem như bài tập.

Tổng kết chương VII: Với sự giới thiệu mô hình máy Turing như là một mô hình của sự tính toán, người ta còn đi tới khái niệm về độ phức tạp của tính toán hay “độ khó” của các bài toán. Nghiên cứu về độ phức tạp của tính toán là một hướng nghiên cứu hiện đại trong Tin học, nó có ý nghĩa lớn lao về lý thuyết cũng như thực hành. Kết thúc chương này, sự phân lớp ngôn ngữ theo nguyên tắc của Noam Chomsky đã được thể hiện tương đối rõ ràng.

BÀI TẬP CHƯƠNG VII

7.1. Thiết kế máy Turing nhận diện ngôn ngữ:

a) { 0n 1n 0n | n ³ 1}

b) {ww R | w Î (0+1)*}

c) Tập hợp các chuỗi chứa 0 và 1, có số số 0 và số số 1 bằng nhau.

7.2. Thiết kế máy Turing tính các hàm số nguyên:

a) f(n) = n2

b) f(n) = 2n

c) f(n) = n !

7.3. Xây dựng văn phạm không hạn chế (loại 0) sinh ra các ngôn ngữ sau:

a) { ww | w Î (0+1)*}

b) { 0k | k = i2 và i ³ 1}

c) { 0i | i không là số nguyên tố}

BÀI TẬP LẬP TRÌNH

7.4. Viết chương trình máy tính mô phỏng hoạt động của các TM thiết kế trong bài tập 7.1 và 7.2.