Bài giảng Lý thuyết tính toán - Chương 3: Văn phạm và ôtômat đẩy xuống

 đó
 Một đầu ghi để có thể ghi lên DSĐX
50/77
Hoạt động của ôđx
Hoạt động đoán nhận Ôđx không đơn định như sau :
 Tương tự một ôhh không đđ,
câu vào w* được đặt ở mút trái trên băng vào
 Lúc đầu, đầu đọc ở vị trí w(1)
DSĐX rỗng và ôđx đang ở trạng thái đầu q0
Đầu đọc đọc lần lượt từng ký tự của w trên băng
Ôđx nhìn một phần câu trên đỉnh DSĐX (Top) để thay thế
(Pop-Push) bằng cách ghi (đè) lên một dãy ký tự
Ôđx di chuyển đầu đọc qua phải và thay đổi trạng thái
Ôhh dừng khi mọi ký tự của w đã được đọc hết
và thừa nhận câu, hoặc hóc giữa chừng
51/77
Minh hoạ hoạt động của ôđx
Trước : trên đĩnh DSĐX là 
Câu vào trên băng w=anbn
a a ba b b
qi 

a a ba b b
qi+1 

Sau : trên đĩnh DSĐX là 
R/W Head 
52/77
Định nghĩa hình thức ôđx
 Một NSA là một bộ 7 : M  Q, , , , Z, q0, A, trong đó :
 Q là tập hợp hữu hạn các trạng thái
  là bảng chữ vào hữu hạn Input Alphabet
  là bộ chữ đẩy xuống hữu hạn Stack Alphabet
 Z   là ký tự đầu của DSĐX Initial Stack Symbol
 q0  Q là trạng thái đầu
 F  Q là tập các trạng thái cuối
   ((Q  *  *)  (Q  *)) là quan hệ chuyển tiếp
gồm một tập hợp hữu hạn các quan hệ ((p, u, ), (q, ))
p, q  Q ; u  * ; ,   *
Có thể viết gọn quan hệ thành puq
53/77
Mô tả
 Bộ chữ đẩy xuống  của ôđx :
 Chứa tập hợp các ký tự sẽ được đưa vào trong DSĐX
 Không nhất thiết phân biệt  với  (có thể   )
 Ký tự Z là ký tự đầu hay nội dung ban đầu của DSĐX
 Các chuyển tiếp ((p, u, ), (q, )) trong  :
 Tương tự một ôhh không đđ
 Có thêm hoạt động chuyển tiếp của DSĐX :
 Câu vào bắt đầu bởi tiền tố u : w = uw’
 Ôtômat chuyển từ trạng thái p sang trạng thái q
 Phần câu  đang nằm trên đỉnh của DSĐX
 Đầu đọc đọc xong tiền tố u của câu vào
 Thay thế  trên đỉnh DSĐX bởi câu phần 
54/77
Các khái niệm
 Người ta cũng định nghĩa một cách hình thức
tương tự các ôhh, nhưng có mặt của DSĐX các khái niệm :
 Cấu hình
 Chuyển tiếp một bước
 Chuyển tiếp nhiều bước 
 Ôđx đoán nhận câu vào
 NN được thừa nhận bởi ôđx
10
55/77
Ôđx thừa nhận câu vào
 Cho ôđx MQ, , , , Z, q0, F và một câu vào w*
 Ôđx thừa nhận câu w nếu quá trình đoán nhận đạt đến một 
trong các trạng thái kết thúc :
 Phần câu xử lí còn lại rỗng
 (q0, w, Z) ├*M  p, ,   với p  F
 Do ôđx M không đơn định, nên có thể có
nhiều phép đoán nhận khác nhau trên cùng một câu vào
56/77
Biểu diễn ôtômat đẩy xuống
 Cho ôtômat M  Q, , , , Z, q0, F
 Có thể biểu diễn M tương tự các ôhh như sau :
 Bằng cách liệt kê hết các thành phần của M
 Dùng đồ thị
 Thực tế, người ta thường dùng cách biểu diễn đồ thị
khi số trạng thái của ôtômat không quá lớn
57/77
Dùng đồ thị biểu diễn ôđx 
 Cho ôđx M  Q, , , , Z, q0, F
quy ước vẽ M như sau :
q
> p
q
u, |
p
p là trạng thái đầu, p = q0
(p, u, , q,   
q là trạng thái cuối, q  F 
58/77
Ví dụ 1 : ôđx đơn định 
 Ngôn ngữ { anbn | n  0 } được thừa nhận bởi ôđx M1 :
Q  { s, p, q }   { a, b }   { A }, F  { q }
 gồm các chuyển tiếp :
s, a,    s, A s, b, A   p, 
s, , Z   q,  p, b, A  p,  p, , Z  q, 
p
b, A|
q> s
a, |A b, A|
, Z|
, Z|
Vừa đọc vừa ghi nhớ
A vào DSĐX
n con a đã đọc
 i 
Đọc từng con b 
và xoá đỉnh DSĐX
là con A
 t 
 ỉ 
l 
Xử lý câu rỗng
  anbn
l r
59/77
Ôđx M1 đoán nhận câu anbn
 Cho câu vào a3b3, ôđx M1 thực hiện đoán nhận như sau :
saaabbbZ ├M1 saabbbAZ ├M1 sabbbAAZ ├M1 sbbbAAAZ ghi nhớ a
├M1 pbbAAZ ├M1 pbAZ ├M1 pZ kiểm tra b
q thừa nhận
 Như vậy M1 thừa nhận các câu anbn, n0, ta viết L(M1) = anbn
p
b, A|
q> s
a, |A b, A|
, Z|
, Z|
60/77
Cách vẽ khác của ôđx M1
Có thể vẽ ôđx M1 theo cách khác như sau :
p
b, A|
q> s
a, Z|AZ
b, A|
, Z|
, Z|
a, A|AAZ
11
61/77
Ví dụ 2 : ôđx không đơn định
 Ngôn ngữ {wwR} được thừa nhận bởi M2 như sau :
Q  { s, p, q}   { a, b }   { A, B } F  { q }
 chứa các chuyển tiếp :
s, a,   s, A s, ,   p,  p, b, B  p, 
s, b,   s, B p, a, A  p,  p, , z  q, 
Vừa đọc vừa ghi nhớ
A, B vào DSĐX
các con a, b đã đọc
 i 
, 
 , 
Đọc từng con a, b 
và xoá đỉnh DSĐX
là con A, B
 t , 
 ỉ 
l , 
p
, |
q> s
a, |A a, A|
, Z|
, Z|Xử lý câu rỗng
  wwR
l r b, |B b, B|
62/77
Ôđx M2 thừa nhận câu abba
 Cho câu vào abba, ôđx M2 thực hiện đoán nhận như sau :
sabbaZ ├M1 sbbaAZ ├M2 sbaBAZ ghi nhớ a, b đã đọc
├M2 pbaBAZ chuyển dịch không đơn định
├M2 paAZ ├M2 pZ kiểm tra a, b để xoá A, B trên DSĐX
q thừa nhận câu abba (thành công)
p
, |
q> s
a, |A a, A|
, Z|
, Z|
Chuyển dịch 
không đơn định
 ị 
 ị
b, |A b, B|
63/77
Ôđx M2 đoán nhận câu abba thất bại
 Vẫn câu vào abba, ôđx M2 thực hiện đoán nhận như sau :
sabbaZ ├M1 sbbaAZ ├M2 sbaBAZ ghi nhớ a, b đã đọc
├M2 saBBAZ ├M2 sABBAZ hóc : không thể đọc tiếp a hay b !
├M2 pABBAZ ??? cũng vẫn hóc : không thể đọc tiếp
ôtômat không thừa nhận câu abba !
p
, |
q> s
a, |A a, A|
, Z|
, Z|
Chuyển dịch 
không đơn định
 ị 
 ị
b, |B b, B|
64/77
Ví dụ ôđx kđđ hai trạng thái 
 Có thể xây dựng ôđx M3 gồm chỉ hai trạng thái
M3 thừa nhận ngôn ngữ wwR với DSĐX rỗng :
Q  { s, p }   { a, b }   { A, B } F  { p }
 gồm các chuyển tiếp : 
s, a,   s, A  s, ,   p,  p, b, B  p, 
s, b,   s, B p, a, A  p,  p, , Z  p, 
, |
a, |A a, A|
b, |B
b, B|
, Z|
, Z|
p> s
65/77
Văn phạm phi ngữ cảnh
 Theo phân cấp VP của Chomsky, VP phi ngữ cảnh (PNC) :
G   N, , R, S 
gồm các sản xuất dạng A  
với A  N,   (N)* = V*, không có hạn chế gì trên 
 Từ G, có thể định nghĩa NN PNC :
L = L(G)
 Một NN L là PNC nếu tồn tại một VP PNC sản sinh ra L 
66/77
Ví dụ các VP2
 Dưới đây làmột số VP PNC :
 G1 { S  aSb |  } L(G1) = anbn, n0 
 G2 { S  aSa | bSb |  } L(G1) = wwR
 G3 { S  aB | bA |  A  bAA | aS B  bS | aBB }
L(G3) gồm các câu chứa cùng số chữ a và chữ b trong một 
thứ tự nào đó
 G4 { S  aAS | a A  SbA | SS | ba }
L(G4) = ?
12
67/77
Quan hệ giữa VP2 và ôđx
 Các ngôn ngữ thừa nhận bởi các ôtômat đẩy xuống có thể 
được sinh bởi các văn phạm PNC và ngược lại
 Định lý :
Một ngôn ngữ là PNC nễu
ngôn ngữ đó được thừa nhận bởi một ôtômat đẩy xuống
L = L(M) = L(G) với G là VP2 và M là ôđx
68/77
Tính chất của các ngôn ngữ PNC
 Cho L1 và L2 là hai NN PNC, ta có các tính chất sau :
 Các ngôn ngữ sau là phi ngữ cảnh :
 L1  L2 phép hợp của hai NN PNC
 L1 . L2 phép ghép tiếp hai NN PNC
 L1* lấy bao đóng của một NN PNC
 Ngôn ngữ :
 L1  L2 phép giao của hai NN PNC
không hẳn là phi ngữ cảnh !
 Tuy nhiên ngôn ngữ :
 LR  L2 là PNC với LR là NNCQ và L2 là PNC
69/77
Vấn đề tạo sinh câu của VP PNC
 Cho VP PNC G  (N, , R, S) có L = L(G)
 Khi áp dụng các sản xuất để tạo sinh câu, thứ tự áp dụng
là không quan trọng :
 Xuất phát từ ký tự đầu S, có thể áp dụng tuỳ ý các sản xuất,
hay dùng các dẫn xuất khác nhau trong G đều có thể tạo ra 
cùng một câu
 Tính “phi ngữ cảnh” thể hiện ở chỗ : một ký tự không kết 
thúc AN có thể đựơc thay thế độc lập với các ký tự bao 
xung quanh (trước A và sau A), không phụ thuộc vào “ngữ
cảnh”
 Tính không quan trọng về thứ tự khi áp dụng các sản xuất 
là đặc trưng của các NN PNC
70/77
Ví dụ có nhiều cách suy dẫn 
 Cho văn phạm G :
G { S  SS 1 | aSa 2 | bSb 3 |  4 } (đánh số các sản xuất)
 Với câu w=aabaab,
có thể có 10 cách suy dẫn khác nhau để sinh ra w :
Cách 1 (dãy các SX là 124324) :
S 1 SS 2 aSaS 4 aaS 3 aabSb 2 aabaSab 4 aabaab
Cách 2 (dãy các SX là 132424) :
S 1 SS 3 SbSb 2 SbaSab 4 Sbaab 2 aSabaab 4 aabaab
V.v...
 Sự khác nhau của các cách suy dẫn ra w
là thứ tự áp dụng các sản xuất của G 
71/77
Ví dụ hiện tượng nhập nhằng
 Trong NN tự nhiên nói chung, tiếng Việt nói riêng,
 thường xuyên xảy ra các hiện tượng nhập nhằng
 Nhập nhằng về từ loại :
 Học sinh học sinh học
 Nhập nhằng về nghĩa :
 Ông già đi nhanh quá
 Nhập nhằng về phát âm :
 Bà Ba bốn bận bán bánh
 Nhập nhằng về tiếng Việt không dấu :
 Nha may Co khi Gia Lam
72/77
Văn phạm nhập nhằng 
 Cho VP PNC G :
 VP G đgl nhập nhằng (Ambiguous Grammar) khĩ
Có hai cây phân tích cùng suy dẫn cho một câu wL(G)
 Cho L là NN PNC :
 NN L đgl nhập nhằng cố hữu
(Inherently Ambiguous Language) khĩ
NN L được sinh bởi nhiều VP khác nhau
L = L(G1) = L(G2) = ...
và tất cả các văn phạm G1, G2 ... này đều nhập nhằng
 Cho VP PNC G nhập nhằng :
 Có thể biến đổi G về G’ tương đương, L(G’) = L(G), sao cho
 G không còn là văn phạm nhập nhằng
13
73/77
Ví dụ văn phạm nhập nhằng
 Cho VP PNC G có các SX :
{ E  E+E 1 | E*E 2 | a 3 }
 VP G nhập nhằng vì có hai cây PT sinh ra câu w=a+a*a :
 E 1 E+E 3 a+E 2 a+E*E 3 a+a*E 3 a+a*a
 E 2 E*E 1 E+E*E 3 a+E*E 3 a+a*E 3 a+a*a
E
E
E
a*a a+
1
3
2
E
E E3 3
E
E
E
a + aa *
1
2
E E3 3 3
E
74/77
Một số ví dụ khác về VP nhập nhằng
 Các VP sau đây đều :
 G1 { S  aSa | bSb | a | b |  }
 G2 { S  aS | Sa | a }
 Bài tập :
Cho ví dụ minh họa tính nhập nhằng 
của G1 và G2 ?
i
í i í
75/77
Bài tập chương 4
1. Mô tả các ôhh đẩy xuống thừa nhận các NN sau đây :
a) anbncm
b) anbmcn
2. Tìm văn phạm PNC sản sinh các ngôn ngữ sau đây :
a) anbncm
b) anbmcn
3. Chứng minh rằng NN { aibjck | i  j hoặc i  k } là PNC
Phần bù của ngôn ngữ này cũng là PNC ?
Gợi ý : hội của các ngôn ngữ PNC cũng là PNC
4. Chứng minh rằng NN { an | n là số nguyên tố }
không là PNC
76/77
Hướng dẫn 1
 Mô tả các ôhh đẩy xuống thừa nhận NN L = anbncm
 Vẽ Ođx thừa nhận anbn (đã biết cách vẽ)
 Vẽ tiếp Ođx chỉ đọc cm (không cần ghi nhớ vào DSĐX)
77/77
Hướng dẫn 2
Tìm văn phạm PNC sản sinh ngôn ngữ anbncm
Ý tưởng : vận dụng VP G’ mà L(G’) = anbn sau đó thêm cm
 Xây dựng G’ { S  aSb |  } có L(G’) = anbn
 Thêm cm để nhận được G như sau :
G { S  AB A  aAb |  B  cB | } 
 Quả thật, L(G) = anbncm