<< Chapter < Page Chapter >> Page >

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

BỔ ĐỀ 7.1: Nếu L là G(M1) với TM M1 nào đó thì L là tập đệ qui liệt kê

Chứng minh

Ta xây dựng M2 có nhiều hơn M1 một băng, M2 sẽ thực hiện tương tự M1, M2 dùng tất cả các thành phần của M1 chỉ trừ băng input của M1, nhưng khi M1 in # trên băng output của M1 thì M2 lấy input của M2 so sánh với từ vừa được sinh trên băng output của M1. Nếu giống thì M2 chấp nhận, ngược lại M2 tiếp tục làm tương tự M1. Rõ ràng M2 chấp nhận input w nếu và chỉ nếu M1 sinh ra w, vậy G(M1) là tập đệ qui liệt kê.

Chứng minh điều ngược lại của bổ đề trên là khó khăn hơn. Giả sử M1 là bộ nhận dạng của một tập hợp đệ qui liệt kê L  * nào đó. Nếu ta cố gắng thiết kế một bộ sinh ra L có thể sinh mọi từ thuộc * theo thứ tự nào đó là w1, w2, ... , ta cho chạy M1 trên w1, nếu M1 chấp nhận thì sinh ra w1. Rồi chạy M1 với w2, ..., cứ lần lượt như thế với mọi từ. Phương pháp này chỉ đúng nếu M1 dừng trên mọi input. Tuy nhiên, do có các tập đệ qui liệt kê nhưng không đệ qui vì vậy M1 có thể không dừng với một input wi nào đó và tất nhiên ta sẽ không bao giờ xét được các từ sau đó wi+1, wi+2, ... ngay cả khi M1 chấp nhận chúng.

Từ phân tích trên, ta thấy vấn đề đặt ra là phải thiết kế bộ sinh sao cho nó có thể tránh được trường hợp trên. Để làm như vậy trước hết ta đánh số thứ tự các từ thuộc * rồi ta sinh ra từng cặp số nguyên dương (i, j). Việc sinh ra cặp (i, j) có ý nghĩa như là M1 sinh ra từ thứ i bằng j bước. Cụ thể, ta đánh số các từ trong * theo "thứ tự chuẩn" (canonical order) như sau: liệt kê các từ theo độ dài, với các từ có cùng độ dài được liệt kê theo thứ tự số, tức là nếu  = {a0, a1, ..., ak-1} thì mỗi từ w  * coi như là một số trong hệ k-phân. Ta có thể thiết kế TM sinh ra các từ theo thứ tự chuẩn là không khó khăn gì.

Thí dụ 7.9 :Nếu  = {0,1} thì các từ liệt kê theo thứ tự chuẩn là: , 0, 1, 00, 01, 10, 11, 000, 001, ... Xét cách sinh ra cặp sinh (i, j) sau một lượng thời gian hữu hạn. Nếu sinh theo thứ tự (1, 1), (1, 2), ... thì sẽ không bao giờ sinh được cặp (i, j) với i>1. Thay vào đó ta cho sinh ra cặp (i, j) theo thứ tự i + j, vì số lượng cặp (i, j) thỏa i + j bằng hằng số là hữu hạn nên cặp (i, j) bất kỳ sẽ được sinh ra sau một lượng thời gian hữu hạn, cụ thể ta có thể chứng minh: cặp (i, j) sẽ được sinh ở lần sinh thứ :

(i + j - 1)(i + j - 2) / 2+ i.

Máy Turing sinh ra các cặp sinh (i, j) viết trong hệ nhị phân là dễ dàng được thiết kế và ta gọi máy Turing này là bộ sinh cặp.

ĐỊNH LÝ 7.7 : Một ngôn ngữ là tập đệ qui liệt kê nếu và chỉ nếu nó là G(M2) với TM M2 nào đó.

Chứng minh

Với bổ đề 1 ta chỉ cần chỉ ra rằng nếu L = L(M1) thì L được sinh ra bởi TM M2. M2 tương tự như bộ sinh cặp. Khi (i, j) được sinh ra, M2 sản xuất từ thứ i theo thứ tự chuẩn và làm tương tự M1 trên từ wi với j bước. Nếu M1 chấp nhận từ thứ i với j bước thì M2 sinh ra wi. Chắc chắn rằng M2 không sinh ra từ không thuộc L, đặt w là từ thứ i trong thứ tự chuẩn trên bộ chữ cái L và M1 chấp nhận w bằng j bước. Vì chỉ cần một lượng thời gian hữu hạn để M2 sinh ra bất kỳ từ nào và làm tương tự như M1 nên M2 chắc chắn sinh ra (i, j). Lúc này w sẽ được sinh ra bởi M2. Vậy L = G(M2)

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Giáo trình tin học lý thuyết. OpenStax CNX. Jul 30, 2009 Download for free at http://cnx.org/content/col10826/1.1
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Giáo trình tin học lý thuyết' conversation and receive update notifications?

Ask