Giáo trình môn Ngôn ngữ hình thức

sau: 
 k: print A, 
 k: move right, k: move left, 
 k: if A then go to h, 
 k: stop, 
 Ở đây k và h là các số tự nhiên ký hiệu dòng chỉ thị, còn A là một ký hiệu trên băng. 
 Chương trình là một dãy chỉ thị. Việc thực hiện chương trình thông thường là 
theo thứ tự tự nhiên của cách viết trừ khi gặp lệnh if A then go to h (nếu ký hiệu hiện 
hành trên băng là A thì nhảy đến thực hiện lệnh có nhãn h). Sau đây là chương trình 
mô tả hoạt động của một máy Turing thực hiện phép toán nhân hai: 
 70 
 1: print B, 
 2: move left, 
 3: if 1 then go to 2, 
 4: print 1, 
 5: move left, 
 6: if 1 then go to 5, 
 7: print 1, 
 8: move right, 
 9: if 1 then go to 1, 
 10: stop, 
 Các máy Turing và các hàm có thể tính được bằng máy Turing đóng vai trò quan 
trọng trong lý thuyết thuật toán. Cơ sở cho việc xây dựng một số lý thuyết thuật toán 
từ máy Turing là định đề Church sau đây. 
 Định đề Church: Lớp các hàm có thể tính được bằng thuật toán trùng với lớp 
các hàm có thể tính được bằng máy Turring. 
4.2. Máy Turing phổ dụng 
 Máy Turing phổ dụng là một máy Turing có thể bắt chước sự hoạt động của bất 
kỳ máy Turring nào. Máy Turing phổ dụng U có thể được hiểu như sau: Với một cách 
mã hoá thích hợp ánh xạ chuyển trạng thái của máy Turing bất kỳ và từ ω trên bảng 
chữ vào. Với từ đã mã hoá này, máy Turing phổ dụng U dừng khi và chỉ khi máy 
Turing M dừng với từ ω. Ta có thể xem máy Turing phổ dụng như là mô hình toán học 
của máy tính điện t ử ngày nay. Các máy này th ực hiện công việc bằng cách mã hoá 
chương trình theo ngôn ngữ bên trong được gọi là ngôn ngữ máy. 
 Tập các ký hiệu ghi lên băng là hữu hạn nên ta có thể ký hiệu chúng như sau: S0 
= B,S1, S2,, Sm và có thể mã hoá bằng bộ các chữ số 1. Chẳng hạn, B−1, S1−11, 
 m+1
S2−111, ,Sm−1 . 
 Tương tự, tập các trạng thái là hữu hạn và ta cũng có thể mã hoá chúng: q0−1, 
 n+1
q1−11, q2−111, , qn−1 . 
 Cuối cùng hai ký hiệu L và R cũng có thể mã hoá: L−1, R−11. 
 Bây giờ để mã hoá ánh xạ chuyển trạng thái của máy Turing, ta sử dụng bảng 
biểu diễn ánh xạ này. Trong bảng, các cột được ký hiệu bở i các ký hiệu có thể ghi lên 
băng, các dòng được ký hiệu bởi các trạng thái. Tiếp theo liệt kê các phần tử của bảng 
theo dòng cùng với các chỉ số dòng và cột tương ứng của chúng, thứ tự là các phần tử 
của dòng 1, dòng 2,  từ trái sang phải. Chẳng hạn, trên một dòng xuất hiện bộ <qi, 
 71 
Sj, Sk, C, qh> có nghĩa là δ(qi, Sj) = . Giữa các dãy mã của các bộ năm <qi, 
Sj, Sk, C, qh> có chèn hai chữ số 0 và giữa mã các ký hiệu trong cùng một bộ năm 
được chèn bởi một chữ số 0. Máy Turing M được mã hoá như vậy ký hiệu là [M]. 
 Ta chấp nhận mà không chứng minh ở đây là với máy Turing M bất kỳ tồn tại 
một máy Turing tương đương chỉ có một trạng thái kết thúc, vì vậy ta có thể xem q0 là 
trạng thái đầu và q1 là trạng thái kết thúc duy nhất của máy Turing M. 
 Ví dụ 2.1. Cho máy Turing M với ánh xạ chuyển được cho bởi bảng sau: 
 B S1 
 q0 
 q1 
 q2 
 Các phần tử của bảng được sắp xếp thành dãy dưới đây: 
 , , , 
 Dãy này sẽ được mã hoá dưới dạng xâu nhị phân: 
 [M] = 10101101101100101101101101001101101101011100111011011010111 
 Nếu trên băng vào có ω=S1S1BS1 thì mã tương ứng của nó là: 
 [ω] = 1101101011 
 - Hoạt động của máy Turing phổ dụng: 
 Bây giờ giả sử máy Turing M có n trạng thái và bảng chữ ghi lên băng có m ký 
hiệu, thêm vào đó các ký hiệu, các trạng thái và ánh xạ chuyển của M được mã hoá 
như đã nói ở trên. Mô hình hoá hoạt động của máy Turing M bằng một máy Turing 
phổ dụng U có thể mô tả khái quát như sau: Trước hế t [M] và [ω] cần phải được ghi 
lên băng của máy Turing phổ dụng U theo quy cách sau đây. Ký hiệu X được ghi lên 
băng chia băng thành hai nửa vô hạn. Nửa băng bên phải được dành ra ba đoạn kề 
nhau kể từ vị trí ký hiệu ngay sau X: Đoạn đầu tiên được gọi là Buffer gồm n + m + 2 
vị trí ký hiệu và tất cả được nhận ký hiệu 0; đoạn tiếp theo được gọi là vùng mã hoá 
của M, bắt đầu bởi ký hiệu Y, tiếp sau Y là [M] và được kết thúc bởi ba chữ số 0; đoạn 
sau cùng được gọi là đoạn mã của ω, bắt đầu bởi ký hiệu Z và tiếp theo là [ω]. Hình 
ảnh của băng lúc đầu là như sau: 
 72 
 Buffer phục vụ cho việc ghi nhận hình trạng của M trong từng bước. Ta có thể 
sao chép vào vùng này trạng thái bên trong và mã hoá của ký hiệu đang đọc. Ký hiệu 
Y thường đứng trước bộ năm xác định trạng thái hiện hành của M, ký hiệu hiện hành 
trên băng, hướng chuyển động của đầu đọc trên băng. Z đánh dấu ký hiệu đang đọc 
trên băng của M. 
 Quá trình tính toán trong U mô phỏ ng hoạt động của máy Turing M với xâu vào 
ω đượ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ư đã 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 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: 
 73 
 - 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. 
 - 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. 
 74 
4.3. Vấn đề không giải đƣợc bằng thuật toán 
 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. 
4.3.1. Đị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’) = ̅. 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’) = ̅ cũng 
là ngôn ngữ đệ quy. 
4.3.2. Định lý 3.2 
 Nếu L là ngôn ngữ đệ quy đếm được trên bảng chữ Σ và phần bù ̅ của nó cũng 
là đệ quy đếm được thì L là đệ quy. 
 Chứng minh: 
 Giả sử M1, M2 là các máy Turing sao cho T(M1) = L và T(M2) = ̅. 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 ω ∈ ̅ . 
Nếu ω ∈ ̅ 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. 
 75 
4.3.3. Đị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. 
4.3.4. Đị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 
 76 
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. 
4.3.5. Đị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. 
 77 
 TÀI LIỆU THAM KHẢO 
1. Nguyễn Văn Ba (2006). Lý thuyết ngôn ngữ và tính toán. Nxb Đại học Quốc gia, 
Hà Nội. 
2. Đỗ Đức Giáo, Đặng Huy Ruận (1991). Văn phạm và ngôn ngữ hình thức. Nxb Khoa 
học Kỹ thuật, Hà Nội. 
3. Lê Mạnh Thạnh (1998). Nhập môn ngôn ngữ hình thức và Otomat. Nxb Giáo dục, 
Đà Nẵng. 
 78