Bài giảng Otomat và ngôn ngữ hình thức - Nguyễn Văn Định

ợc chia ra các pha thích hợp với việc dịch chuyển các hình trạng của M. 
Một giai đoạn (pha) hoạt động của máy Turing phổ dụng U có thể tóm tắt như sau. 
Đầu tiên sao chép vào Buffer một khối các ký hiệu 1 nằm ngay sau Y (gọi là khối Y), sau đó 
ghi vào cuối khối vừa được chép một ký hiệu X, tiếp theo xoá ký hiệu Y, chạy sang phải tìm 
ký hiệu Z và sao chép khối ký hiệu 1 ngay sau Z (gọi là khối Z) vào Buffer ngay sau ký hiệu 
X rồi ghi lại ký hiệu Y trước [M]. Như vậy sau giai đoạn này trong Bufffer chứa mã của trạng 
thái và ký hiệu hiện hành của máy Turing M. Bước tiếp theo, máy Turing phổ dụng U so sánh 
hai khối ký hiệu 1 liên tiếp nhau sau Y với nội dung Buffer. Nếu trùng nhau thì tìm được bộ 
năm cần tìm. Nếu ngược lại thì tìm đến mã hoá của bộ năm tiếp theo sau Y và lại tiếp tục so 
sánh. Trong trường hợp giữa các bộ năm mô tả M không tìm thấy bộ nào thích hợp thì U 
dừng. Ngược lại, nếu tìm được bộ năm cần tìm thì xoá nội dung buffer rồi chuyển Y đến trước 
phần tử thứ ba trong bộ năm đó. Đổi nội dung của khối sau Z bởi nội dung của khối sau Y và 
chuyển Y đến trước phần tử thứ tư của bộ năm. Sau khi đã đọc xong phần tử thứ tư mà nó xác 
định hướng chuyển động của đầu đọc/ghi của M và U chuyển ký hiệu Y đến sau phần tử trước 
phần tử thứ năm. Tuỳ thuộc vào nội dung của khối thứ tư (một ký hiệu 1 hay hai ký hiệu 1) U 
chuyển Z qua phải hay qua trái một khối. Nếu Z lúc đầu nằm ở tận cùng trái của băng ghi và 
M cần dịch chuyển sang phải thì U đẩy mã của từ sang phải và ghi mã hoá của ký hiệu trắng 
vào sau Z. Nếu Z nằm tận cùng phải của băng và cần chuyển sang phải, khi đó U ghi mã của 
ký hiệu trắng vào cuối từ. Khi hoàn thành các công việc trên khối ký hiệu 1 đứng sau Y, ký 
hiệu trạng thái hiện hành của M, còn khối sau Z xác định ký hiệu M cần đọc tiếp theo. Như 
vậy, giai đoạn tiếp theo của việc mô phỏng bước tiếp theo của M có thể bắt đầu. 
Các giai đoạn hoạt động của máy Turing phổ dụng U mô hình hoá hoạt động từng 
bước của máy Turing M như dã chỉ ở trên. Ngoài ra, U còn thực hiện công việc sau đây. Đầu 
tiên U thay tất cả các ký hiệu 0 trên ba đoạn của băng vào bằng các khoảng trắng, cuối công 
 80
việc, khi M dừng máy U còn kiểm tra liệu trạng thái cuối của M có phải là trạng thái kết thúc 
hay không. 
Các pha của một máy Turing phổ dụng U được chia thành chín phần, với đồ thị 
chuyển trạng thái phù hợp cho việc mô tả máy, được cho trong hình dưới đây: 
− Phần 1: Thay các ký hiệu 0 bởi ký hiệu B và đầu đọc/ghi chuyển đến trước Y. 
− Phần 2: Sao chép mã của trạng thái hiện hành vào buffer. 
− Phần 3: Sao chép mã của ký hiệu cần đọc trên băng của M vào buffer. 
− Phần 4: Đặt X và Y vào trước buffer và trước ký hiệu của [M]. 
− Phần 5: Tìm bộ năm có mã của trạng thái và ký hiệu trên băng trùng với buffer. 
 81
− Phần 6: Xoá buffer. 
− Phần 7: Thay mã ký hiệu đã đọc bằng mã ký hiệu mới của M. 
− Phần 8: Đẩy Z sang phải hay sang trái một khối mà mã ký hiệu của khối đó sẽ được đọc 
trong pha tiếp theo. Nếu cần thì ghi mã một khoảng trắng vào phải hoặc trái từ trên băng của 
M. 
− Phần 9: Máy Turing phổ dụng U dừng ở trạng thái kết thúc khi và chỉ khi M dừng ở trạng 
thái kết thúc. Đồng thời trong vùng mã hoá của từ trên băng sẽ chứa mã của từ đáng ra còn lại 
trên băng của M, còn mã của trạng thái cuối của M có thể thấy trên buffer. 
§3. Vấn đề không giải được bằng thuật toán 
3.1 Mở đầu: 
Trong toán học thường gặp vấn đề cần xác định liệu một phần tử của một lớp vô hạn 
nào đó có một số tính chất đã cho hay không. Chẳng hạn, ta có thể hỏi liệu hai số tự nhiên cho 
trước có nguyên tố cùng nhau hay không, hoặc là một máy Turing có dừng sau một số hữu 
hạn bước hay không, … Các vấn đề trên được gọi là vấn đề thuật toán và có thể quy về vấn đề 
là liệu một từ trên bảng chữ nào đó có thuộc vào một ngôn ngữ hình thức đã cho hay không. 
Một bài toán được gọi là không giải được bằng thuật toán nếu không tồn tại một máy 
Turing nào sau một số hữu hạn bước xác định được liệu một sự mã hoá cụ thể nào đó của bài 
toán có thuộc ngôn ngữ hình thức đã cho hay không. Trong trường hợp ngược lại thì bài toán 
được gọi là giải được bằng thuật toán. Như vậy, một vấn đề giải được bằng thuật toán nếu và 
chỉ nếu ngôn ngữ hình thức mô tả nó là đệ quy. 
Sau đây ta sẽ nghiên cứu một vài tính chất của ngôn ngữ đệ quy và đệ quy đếm được. 
Việc chứng minh các tính chất này khá phức tạp nên ta không đi sâu vào chi tiết. 
3.2. Định lý 3.1 Phần bù của một ngôn ngữ đệ quy là ngôn ngữ đệ quy. 
Chứng minh: Giả sử L là một ngôn ngữ đệ quy trên bảng chữ Σ. Điều này có nghĩa là tồn tại 
một máy Turing M mà với từ ω∈Σ* tuỳ ý nó dừng sau một số hữu hạn bước và T(M) = L. 
Thay tập trạng thái kết thúc của M bằng phần bù của nó, ta được một máy Turing mới M’. 
Dưới tác động cùng một từ, M’ dừng với trạng thái kết thúc khi và chỉ khi dưới tác động của 
từ đó M dừng với trạng thái không kết thúc. Điều này dẫn đến T(M’) = L . Do M’ dừng sau 
một số hữu hạn bước với mọi từ vào nên T(M’) = L cũng là ngôn ngữ đệ quy. 
3.3. Định lý 3.2 Nếu L là ngôn ngữ đệ quy đếm được trên bảng chữ Σ và phần bù L của nó 
cũng là đệ quy đếm được thì L là đệ quy. 
 82
Chứng minh: Giả sử M1, M2 là các máy Turing sao cho T(M1) = L và T(M2) = L . Ta cần xây 
dựng máy Turing M’ mà nó mô hình hoá đồng thời sự hoạt động của M1, M2. Điều ta cần có 
là dưới tác động của từ ω, máy Turing M’ ngừng hoạt động khi và chỉ khi M1 hoặc M2 đoán 
nhận từ ω. Ta muốn M1 dừng với trạng thái kết thúc, còn M2 dừng với trạng thái không kết 
thúc. Việc xây dựng này là có thể thực hiện được và với mọi từ ω máy Turing M’ sau một số 
hữu hạn bước sẽ dừng. Nếu ω∈Σ* thì ω∈L hoặc ω∈L . Nếu ω∈L thì M2 sẽ đoán nhận ω sau 
một số hữu hạn bước. Từ đó nếu M1 không dừng sau một số hữu hạn bước thì M’ phải hoàn 
thành công việc của mình trong thời gian hữu hạn. Như vậy T(M1) = L là đệ quy. 
3.4. Định lý 3.3 Tồn tại một ngôn ngữ đệ quy đếm được nhưng không đệ quy. 
Chứng minh: Xét ngôn ngữ T(U) được đoán nhận bởi máy Turing U. Khi đó T(U) là đệ quy 
đếm được. 
 Giả sử T(U) là đệ quy. Điều này có nghĩa là tồn tại một máy Turing M (không đòi hỏi 
là trùng với U) sao cho T(M) = T(U) và sẽ dừng sau một số hữu hạn bước dưới tác động của 
mọi từ trên bảng chữ vào. Ta xây dựng máy Turing M’ như sau: 
 Giả sử ω là một từ trên bảng chữ vào của M’. Trước hết M’ cho mã [ω] của ω, đồng 
thời trên cơ sở sắp xếp các từ trên bảng chữ vào tìm chỉ số i của ω (số thứ tự của ω trong dãy 
là i). Tiếp theo ứng với các chỉ số i, máy Turing M’ thiết lập sự mô tả mã của máy Turing thứ 
i trong dãy các máy Turing M1, M2, …Cuối cùng M thiết lập sự mô tả chuẩn của từ ωi và Mi, 
. M’ bắt chước sự hoạt động của máy Turing M với từ mà theo giả thiết nó tồn 
tại, đoán nhận ngôn ngữ T(U) và dừng sau một số hữu hạn bước đối với mọi từ trên bảng chữ 
vào. Nếu M kết thúc sự hoạt động với trạng thái không kết thúc thì khi đó M’ chuyển sang 
một trạng thái kết thúc riêng và dừng. Nếu M dừng ở trạng thái kết thúc thì M’ bắt đầu bắt 
chước sự hoạt động của máy Turing mà nó không dừng với mọi từ của bảng chữ vào. 
 Rõ ràng rằng máy Turing M’ đoán nhận từ ω = ωi khi và chỉ khi không đoán nhận 
. Ta biết rằng T(M) = T(U) ={ | ϕ∈T(Mi)}. Đồng thời mọi máy Turing đều có 
mặt trong dãy M1, M2, … và do đó M’ cũng nằm trong dãy này, có nghĩa là tồn tại một số tự 
nhiên h sao cho M’= Mh. 
 Bây giờ ta xem máy Turing M1 hoạt động như thế nào với từ ω1. Ta nhận được 
ω1∈T(M’) khi và chỉ khi ω1∈T(M1). Điều này mâu thuẫn với giả thiết. Vậy T(U) không đệ 
quy. 
Hệ quả 3.1 Tồn tại một ngôn ngữ hình thức nhưng không đệ quy đếm được. 
Chứng minh: Như trong chứng minh của Định lý 4.3.4, T(U) là đệ quy đếm được nhưng 
không đệ quy. Do đó theo Định lý 4.3.3, phần bù của T(U) là không đệ quy đếm được. 
 83
3.5. Định lý 3.4 Một ngôn ngữ hình thức là loại 0 khi và chỉ khi nó là đệ quy đếm được. Điều 
này có nghĩa là lớp ngôn ngữ hình thức loại 0 chính là lớp ngôn ngữ đệ quy đếm được. 
Chú ý: Nhờ vào Định lý 4.3.4, ta thấy rằng có những ngôn ngữ đệ quy đếm được nhưng 
không đệ quy. Với việc mã hoá thích hợp, ta chỉ ra rằng nhiều vấn đề không giải quyết được 
bằng thuật toán. Ta sẽ khảo sát một số vấn đề liên quan đến lớp các ngôn ngữ đệ quy đếm 
được. Chẳng hạn như một ngôn ngữ đệ quy đếm được có rỗng hay không, có hữu hạn hay 
không, có chính quy hay không, có là phi ngữ cảnh hay không và có là cảm ngữ cảnh hay 
không, … Tất cả các ngôn ngữ có tính chất này hình thành lên một lớp con của lớp các ngôn 
ngữ đệ quy đếm được. Khi ta khảo sát một ngôn ngữ có hay không một tính chất đã cho thì 
thực tế ta cần giải quyết vấn đề ngôn ngữ này có thuộc hay không lớp con đã cho của lớp các 
ngôn ngữ đệ quy đếm được. 
 Ta nói rằng một tính chất của các ngôn ngữ đệ quy đếm được là tầm thường nếu hoặc 
mọi ngôn ngữ đệ quy đếm được đều có tính chất này hoặc ngược lại mọi ngôn ngữ đệ quy 
đếm được không có tính chất này. Điều này có nghĩa là lớp con các ngôn ngữ xác định bởi 
tính chất này hoặc bằng rỗng hoặc bằng chính lớp các ngôn ngữ đệ quy đếm được. Như vậy 
các tính chất: một ngôn ngữ đã cho có rỗng hay không, có hữu hạn hay không, có chính quy 
hay không, … là không tầm thường. Có những ngôn ngữ đệ quy đếm được có những tính chất 
trên và có những ngôn ngữ đệ quy đếm được không có tính chất trên. 
 Từ Định lý 4.3.3, ta biết rằng muốn xác định bằng thuật toán việc thực hiện một tính 
chất nào đó thì vấn đề này được giải quyết bằng thuật toán khi và chỉ khi việc phủ định của 
tính chất này cũng được giải quyết bằng thuật toán. 
3.6. Định lý 3.5 Cho trước một tính chất không tầm thường của lớp các ngôn ngữ đệ quy đếm 
được. Khi đó vấn đề xác định rằng một ngôn ngữ có tính chất này hay không là không giải 
quyết được bằng thuật toán. 
Hệ quả 3.2 Việc xác định rằng một ngôn ngữ đệ quy đếm được có là: 
 a) Rỗng, 
 b) Hữu hạn, 
 c) Chính quy, 
 d) Phi ngữ cảnh, 
 e) Cảm ngữ cảnh, 
 f) Đệ quy 
hay không là vấn đề không giải được bằng thuật toán. 
 84