0.6 Máy turing  (Page 14/15)

HỆ QUẢ : Nếu L là tập đệ qui liệt kê thì có một bộ sinh sinh ra mỗi từ trong L đúng một lần.

Tính chất đệ qui của tập sinh

BỔ ĐỀ 7.2: Nếu L là tập đệ qui thì có một bộ sinh in ra các từ của L theo thứ tự chuẩn và không in ra các từ khác.

Chứng minh

Đặt L = L(M1)  * trong đó M1 dừng với mọi input. Ta xây dựng M2 sinh ra L như sau M2 sinh ra các từ thuộc * mỗi lần một từ theo thứ tự chuẩn. Sau khi sinh ra một từ w, M2 làm tương tự M1 trên w. Nếu M1 chấp nhận w thì M2 sinh ra w. Vì M1 chắc chắn dừng nên M2 cũng sẽ dừng sau hữu hạn bước và chắc chắn sẽ xét mỗi từ thuộc *. Vậy M2 sinh ra L theo thứ tự chuẩn.

Điều ngược lại của bổ đề trên cũng đúng, tức là, nếu L được sinh ra theo thứ tự chuẩn thì L là tập đệ qui. Nghĩa là có TM nhận diện M tồn tại, tuy nhiên không có một giải thuật cụ thể cho TM này.

Giả sử M1 sinh ra L theo thứ tự chuẩn. Một ý nghĩ tự nhiên là ta xây dựng M2 làm tương tự M1 trên input w cho tới khi M1 sinh ra w hoặc sinh ra từ sau w (theo thứ tự chuẩn). Trong trường hợp đầu, M2 chấp nhận w, trong trường hợp sau M2 dừng nhưng không chấp nhận w. Rõ ràng nếu L hữu hạn thì M1 có thể không dừng sau khi sinh ra từ cuối cùng trong L (vì theo định lý trên M1 không sinh từ nào không thuộc L). Trong trường hợp này M2 cũng không dừng. Điều này chỉ gặp khi L hữu hạn, nhưng do không có cách xác định TM có sinh ra tập hữu hạn hay không hoặc nếu biết TM sinh ra tập hữu hạn thì cũng không thể biết tập hợp đó là gì. Vậy ta biết là có TM chấp nhận L, nhưng không thể đưa ra một giải thuật cụ thể cho TM này.

ĐỊNH LÝ 7.8 : L là tập đệ qui nếu và chỉ nếu L được sinh ra theo thứ tự chuẩn.

Chứng minh

Ta chỉ cần chứng minh phần nếu.

Khi L hữu hạn thì sẽ có một ôtômát chấp nhận L và vì vậy L được chấp nhận bởi TM luôn luôn dừng trên tất cả các input.

Sự tương đương giữa văn phạm kiểu 0 và máy turing

Họ văn phạm rộng lớn nhất theo sự phân cấp của Noam Chomsky đòi hỏi các luật sinh có dạng   , với ,  là các chuỗi tùy ý chứa ký hiệu văn phạm sao cho   . Lớp văn phạm này được biết như là văn phạm kiểu 0, văn phạm ngữ cấu hay văn phạm không hạn chế.

Thí dụ 7.10 :Cho một văn phạm không hạn chế sinh ra ngôn ngữ

L = { ai  i là lũy thừa dương của 2 } với tập luật sinh như sau :

G ({S, A, B, C, D, E}, {a,  }, P, S)

Với P = {1. S  ACaB

2. Ca  aaC

3. CB  DB

4. CB  E

5. aD  Da

6. AD  AC

7. aE  Ea

8. AE   }

Trong văn phạm trên, biến A và B giữ vai trò là ký hiệu đánh dấu cận trái và cận phải của một chuỗi thuộc ngôn ngữ. C di chuyển từ trái sang phải qua chuỗi các ký hiệu a nằm giữa hai biến A và B, và gấp đôi số ký hiệu a đó lên theo luật sinh (2). Khi C chạm đến cận phải B, nó sẽ thay thế thành D hay E theo luật sinh (3) hoặc (4). Nếu D được chọn thay thế thì D lại quay về trái theo luật sinh (5), cho đến khi gặp cận trái A thì thay thế lại thành C theo luật sinh (6) và cho phép lặp lại chu trình. Còn nếu E được chọn để thay thế, thì theo luật sinh (4), B sẽ biến mất, sau đó E quay về trái theo luật sinh (7) cho đến khi gặp cận trái A thì xóa A và mất đi theo luật sinh (8), cho ra chuỗi có dạng 2i ký hiệu a, với i>0.