Bài giảng Lý thuyết ôtômát và ngôn ngữ hình thức

 đó M = (Q, Σ, Γ, δ, q0, , F) sao cho
q0w M qf f(w), qf ∈ F, ∀ w ∈ D.
„ Ví dụ
„ Cho x, y nguyên dương, thiết kế máy Turing tính x + y.
„ Chúng ta đầu tiên chọn qui ước để biểu diễn số nguyên dương.
„ Ta đã biết cách biểu diễn số nguyên dương bằng chuỗi nhị phân 
và cách cộng hai số nhị phân, tuy nhiên để ứng dụng điều đó
vào trong trường hợp này thì hơi phức tạp một chút.
„ Vậy để đơn giản hơn ta biểu diễn số nguyên dương x bằng 
chuỗi w(x) các số 1 có chiều dài bằng x.
∧w
*_|
Trang 299
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Ví dụ
„ Chúng ta cũng phải quyết định các số x và y vào lúc ban đầu 
được đặt như thế nào trên băng và tổng của chúng xuất hiện 
như thế nào lúc kết thúc sự tính toán.
„ Chúng ta giả thiết rằng w(x) và w(y) được phân cách bằng một 
kí hiệu 0, với đầu đọc ở trên kí tự trái cùng của w(x). Sau khi 
tính toán, w(x + y) sẽ ở trên băng và được theo sau bởi một kí tự
0, và đầu đọc sẽ được đặt trên kí tự trái cùng của kết quả.
„ Chúng ta vì vậy muốn thiết kế một máy Turing để thực hiện sự
tính toán (trong đó qf là một trạng thái kết thúc)
q0w(x)0w(y) qf w(x + y)0,
Q = {q0, q1, q2, q3, qf,}, F = {qf}δ(q0, 1) = (q0, 1, R) δ(q0, 0) = (q1, 1, R) δ(q1, 1) = (q1, 1, R)δ(q1, ) = (q2, , L) δ(q2, 1) = (q3, 0, L) δ(q3, 1) = (q3, 1, L)δ(q3, ) = (qf, , R)
*_|
Trang 300
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Kết hợp các máy Turing cho các công việc 
phức tạp
„ Chúng ta đã thấy máy Turing có thể thực hiện được các phép 
toán cơ bản và quan trọng những cái mà có trong tất cả các máy 
tính.
„ Vì trong các máy tính số, các phép toán cơ bản như vậy là các 
thành phần cơ bản cho các lệnh phức tạp hơn, vì vậy chúng ta ở 
đây cũng sẽ trình bày máy Turing có khả năng kết hợp các phép 
toán này lại với nhau.
„ Ví dụ
„ Thiết kế một máy Turing tính toán hàm sau
f(x, y) = x + y nếu x ≥ y
= 0 nếu x < y
„ Ta xây dựng mô hình tính toán cho nó như sau
Trang 301
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Kết hợp các máy Turing cho các công việc 
phức tạp (tt)
„ Chúng ta sẽ xây dựng bộ so sánh C mà sau khi thực hiện xong 
có kết quả như sau:
qC,0w(x)0w(y) qA,0w(x)0w(y), nếu x ≥ y
qC,0w(x)0w(y) qE,0w(x)0w(y), nếu x < y
trong đó qC,0, qA,0 và qE,0 lần lượt là trạng thái khởi đầu của bộ
so sánh, bộ cộng và bộ xóa.
Bộ so sánh
C
Bộ cộng
A
Bộ xóa
E
x, y
x + y
0
x ≥ y
x < y
f (x, y)
*_|
*_|
Trang 302
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Bài tập
„ Nếu chúng ta xây dựng được các bộ so sánh, bộ cộng và bộ xóa 
thì với mô hình kết hợp như trên chúng ta có thể xây dựng được 
hàm tính toán được yêu cầu.
„ Xây dựng máy Turing thực hiện các phép toán sau
„ Hàm f(x, y) trong slide trên
„ Phép AND, OR, XOR
„ Phép cộng hai số nhị phân
Trang 303
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Luận đề Turing
„ Máy Turing có thể được xây dựng từ các phần đơn giản hơn, 
tuy nhiên khá cồng kềnh cho dù phải thực hiện các phép toán 
đơn giản. Điều này là vì “tập lệnh” của một máy Turing là quá 
đơn giản và hạn chế.
„ Vậy máy Turing có sức mạnh đến đâu và như thế nào trong sự
so sánh với sức mạnh của máy tính ngày nay?
„ Mặc dầu với cơ chế đơn giản nhưng máy Turing có thể giải 
quyết được các bài toán phức tạp mà máy tính ngày nay giải 
quyết được.
„ Để chứng minh điều này người ta đã chọn ra một máy tính điển 
hình, sau đó xây dựng một máy Turing thực hiện được tất cả
các lệnh trong tập lệnh của máy tính (tập lệnh của CPU).
„ Tuy làm được điều này nhưng đó cũng chưa phải là một chứng 
minh chặt chẽ để chứng tỏ máy Turing có sức mạnh ngang 
bằng với các máy tính ngày nay.
Trang 304
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Luận đề Turing (tt)
„ Tuy nhiên cũng không ai đưa ra được phản chứng chứng minh 
rằng máy Turing không mạnh bằng với máy tính ngày nay.
„ Cuối cùng, với khá nhiều bằng chứng mạnh mẽ tuy chưa đủ là
một chứng minh chặt chẽ, chúng ta chấp nhận luận đề Turing 
sau như là một định nghĩa của một “sự tính toán cơ học”
„ Luận đề Turing
„ Bất kỳ cái gì có thể được thực hiện trên bất kỳ máy tính số đang 
tồn tại nào đều có thể được thực hiện bởi một máy Turing.
„ Không ai có thể đưa ra một bài toán, có thể giải quyết được 
bằng những gì mà một cách trực quan chúng ta xem là một giải 
thuật, mà đối với nó không tồn tại máy Turing nào giải quyết 
được.
„ Các mô hình thay thế khác có thể được đưa ra cho sự tính toán 
cơ học nhưng không có cái nào trong số chúng là mạnh hơn mô 
hình máy Turing.
Trang 305
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Giải thuật
„ Luận đề trên đóng một vai trò quan trọng trong khoa học máy 
tính cũng giống như vai trò của các định luật cơ bản trong vật lý 
và hóa học.
„ Bằng việc chấp nhận luận đề Turing, chúng ta sẵn sàng để định 
nghĩa chính xác khái niệm giải thuật, cái mà là khá cơ bản trong 
khoa học máy tính.
„ Định nghĩa 9.5
„ Một giải thuật cho một hàm f: D→ R là một máy Turing M sao 
cho cho một chuỗi nhập d ∈ D trên băng nhập, cuối cùng M
dừng với kết quả f(d) ∈ R trên băng. Một cách cụ thể là:
q0d M qf f(d), qf ∈ F, ∀ d ∈ D.*_|
Trang 306
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Chương 10 Phụ lục
10.1 Một số định nghĩa
10.2 Tổng kết các đối tượng đã học
10.3 Mối quan hệ giữa các đối tượng
10.4 Sự phân cấp các lớp ngôn ngữ hình thức theo Chomsky
10.5 Một số giải thuật quan trọng khác
Trang 307
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Máy Turing không đơn định
„ Định nghĩa 10.6
„ Là máy Turing mà trong đó hàm δ được định nghĩa như sau:
δ: Q × Σ→ 2Q × Σ× {L, R}
„ Định lý 10.5
„ Lớp máy Turing không đơn định tương đương với lớp máy 
Turing chuẩn.
„ Định lý 10.6
„ Tập tất cả các máy Turing là vô hạn đếm được.
Trang 308
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Ôtômát ràng buộc tuyến tính
„ Định nghĩa 10.7
„ Một ôtômát ràng buộc tuyến tính (Linear Bounded Automat -
LBA) là một máy Turing không đơn định M = (Q, Σ, Γ, δ, q0, 
, F), như trong Định nghĩa 10.6, ngoại trừ bị giới hạn rằng Σ
phải chứa hai kí tự đặc biệt [ và ], sao cho δ(qi, [) có thể chứa 
chỉ một phần tử dạng (qj,[, R) và δ(qi, ]) có thể chứa chỉ một 
phần tử dạng (qj,], L). 
„ Bằng lời, khi đầu đọc chạm đến dấu móc vuông ở một trong hai 
đầu nó phải giữ lại và đồng thời không thể vượt ra vùng nằm 
giữa hai dấu móc vuông.
„ Trong trường hợp này chúng ta nói đầu đọc bị giới hạn giữa hai 
dấu móc vuông hai đầu.
Trang 309
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Ôtômát ràng buộc tuyến tính (tt)
„ Định nghĩa 10.7
„ Một chuỗi được chấp nhận bởi một ôtômát ràng buộc tuyến tính 
nếu có một dãy chuyển hình trạng có thể
q0[w] [x1qfx2]
với một qf nào đó ∈ F, x1, x2 ∈ Σ*. Ngôn ngữ được chấp nhận 
bởi lba là tập tất cả các chuỗi được chấp nhận bởi lba.
„ Ví dụ
„ Ngôn ngữ L = {anbncn: n ≥ 0} là một ngôn ngữ ràng buộc tuyến 
tính vì chúng ta có thể xây dựng được một lba chấp nhận đúng 
nó.
*_|
Trang 310
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Ngôn ngữ khả liệt kê đệ qui, đệ qui
„ Định nghĩa 10.8
„ Một ngôn ngữ L được gọi là khả liệt kê đệ qui nếu tồn tại một 
máy Turing M chấp nhận nó.
„ Từ định nghĩa này cũng dễ dàng suy ra được mọi ngôn ngữ mà 
đối với nó tồn tại một thủ tục liệt kê (các phần tử của nó) thì
khả liệt kê đệ qui.
„ Định nghĩa 10.9
„ Một ngôn ngữ L trên Σ được gọi là đệ qui nếu tồn tại một máy 
Turing M chấp nhận nó và dừng đối với w ∈ Σ+. Hay nói cách 
khác một ngôn ngữ là đệ qui nếu và chỉ nếu tồn tại một giải 
thuật thành viên cho nó.
*_|
Trang 311
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Văn phạm
„ Định nghĩa 10
„ Một văn phạm mà mọi luật sinh không cần thõa bất kỳ ràng 
buộc nào tức là có dạng
α → β
trong đó α ∈ (V ∪ T)*V(V ∪ T)*, β ∈ (V ∪ T)* thì được gọi là
văn phạm loại 0 hay là văn phạm không hạn chế.
„ Một văn phạm mà mọi luật sinh có dạng chiều dài vế trái nhỏ 
hơn hoặc bằng chiều dài vế phải tức là có dạng
α → β
 trong đó α ∈ (V ∪ T)*V(V ∪ T)*, β ∈ (V ∪ T)* và |α| ≤ |β| thì 
được gọi là văn phạm loại 1 hay văn phạm cảm ngữ cảnh.
„ Văn phạm phi ngữ cảnh còn được gọi là văn phạm loại 2.
„ Văn phạm chính qui còn được gọi là văn phạm loại 3.
Trang 312
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Tổng kết các lớp đối tượng
LRERecusively EnumerableKhả liệt kê đệ qui
LRECRecusiveĐệ qui
LCSContext-SensitiveCảm ngữ cảnh
LCFContext-FreePhi ngữ cảnh
LDCFDeterministic Context-FreePhi ngữ cảnh đơn định
LLINLinearTuyến tính
LREGRegularChính qui
Kí hiệuCác lớp ngôn ngữ
Trang 313
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Tổng kết các lớp đối tượng (tt)
GURUnRestrictedKhông hạn chế ≡ Loại 0
GCSContext-SensitiveCảm ngữ cảnh ≡ Loại 1
GCFContext-FreePhi ngữ cảnh ≡ Loại 2
GLL và GLRLL(k) và LR(k)Phi ngữ cảnh đơn định: điển 
hình là LL(k) và LR(k)
GLINLinearTuyến tính
GREG ≡ GR-LIN
và GL-LIN
Regular ≡ Right-
Linear và Left-Linear 
Chính qui ≡ Tuyến tính-phải 
và tuyến tính-trái ≡ Loại 3
Kí hiệuCác lớp văn phạm
Trang 314
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Tổng kết các lớp đối tượng (tt)
TMTuring MachineMáy Turing
LBALinear BoundedRàng buộc tuyến tính
NPDANondeterministic Push DownĐẩy xuống không đơn 
định
DPDADeterministic Push Down Đẩy xuống đơn định
FSA (nfa, dfa)Finite StateHữu hạn
Kí hiệuCác lớp ôtômát
Trang 315
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Mối quan hệ giữa các lớp đối tượng
„ Dấu ≡ có nghĩa là theo định nghĩa, còn dấu = có nghĩa là tương 
đương, dấu ⊃ có nghĩa là tập cha (không bằng), dấu ⊂ có nghĩa 
là tập con (không bằng). 
TMGURLRE
⊂ TM⊂ GURLREC
LBAGCSLCS
NPDAGCFLCF
DPDA⊃ LL(k) và LR(k)LDCF
⊂ NPDAGLINLLIN
FSA ≡ DFA = NFAGREC ≡ GL-LIN và GR-LINLREG
ÔtômátVăn phạmNgôn ngữ
Trang 316
Lý thuyết Ôtômát & NNHT - Khoa Công Nghệ Thông Tin
Phân cấp ngôn ngữ theo Chomsky
LREG
LCF
LCS
LRE
Sơ đồ phân cấp đơn giản
LREG
LDCF
LCF
LCS
LREC
LRE
Sơ đồ phân cấp chi tiếtLREGLLIN
LCF
LDCF
Sơ đồ phân cấp trong lớp PNC