<< Chapter < Page Chapter >> Page >

Thí dụ 6.4 :Xây dựng CFG G tương đương sinh ra ngôn ngữ được chấp nhận bởi PDA sau :

M ( {q0, q1}, {0, 1}, {Z0, X}, d, q0­, Z0, Æ )

với d được cho như sau :

1) d (q0, 0, Z0) = {(q0, XZ0)}

2) d (q0, 0, X) = {(q0, XX)}

3) d (q0, 1, X) = {(q1, )}

4) d (q1, 1, X) = {(q1, )}

5) d (q1, , x) = {(q1, )}

6) d (q1, , Z0) = {(q1, )}

Ta xây dựng CFG G (V, {0, 1}, P, S) sinh ra N(M) với các thành phần như sau :

V = { S, [q0, X, q0], [q0, X, q1], [q1, X, q0], [q1, X, q1],

[q0, Z0, q0], [q0, Z0, q1], [q1, Z0, q0], [q1, Z0, q1]}

Tập luật sinh P chứa các luật sinh có dạng :

Các luật sinh cho ký hiệu bắt đầu S : S ® [q0, Z0, q0] | [q0, Z0, q1]

Các luật sinh cho các biến khác trong V được xây dựng từ các hàm chuyển của PDA như sau :

d1) [q0, Z0, q0] ® 0 [q0, X, q0][q0, Z0, q0]

| 0 [q0, X, q1][q1, Z0, q0]

[q0, Z0, q1] ® 0 [q0, X, q0][q0, Z0, q1]

| 0 [q0, X, q1][q1, Z0, q1]

d2) [q0, X, q0] ® 0 [q0, X, q0][q0, X, q0]

| 0 [q0, X, q1][q1, X, q0]

[q0, X, q1] ® 0 [q0, X, q0][q0, X, q1]

| 0 [q0, X, q1][q1, X, q1]

d3) [q0, X, q1] ® 1

d4) [q1, Z0, q1] ® 

d5) [q1, X, q1] ® 

d6) [q1, X, q1] ® 1

Nhận xét rằng không có luật sinh nào cho các biến [q1, X, q0] và [q1, Z0, q0]. Vì tất cả các luật sinh cho biến [q0, X, q0] và [q0, Z0, q0]đều có chứa [q1, X, q0] hoặc [q0, Z0, q0]ở vế phải, nên sẽ không thể có chuỗi ký hiệu kết thúc nào có thể được dẫn ra từ các biến [q0, X, q0] hoặc [q0, Z0, q0]. Loại bỏ 4 biến này ra khỏi tập biến V và xóa các luật sinh có liên quan đến chúng trong tập P, ta thu được văn phạm có dạng như sau:

S ® [q0, Z0, q1]

[q0, Z0, q1] ® 0 [q0, X, q1][q1, Z0, q1]

[q0, X, q1] ® 0 [q0, X, q1][q1, X, q1]

[q0, X, q1] ® 1

[q1, Z0, q1] ® 

[q1, X, q1] ® 

[q1, X, q1] ® 1

Câu hỏi :

?

Sinh viên hãy dùng các kiến thức đã học trong chương trước (ĐỊNH LÝ 5.2)

để viết một văn phạm tương đương với văn phạm trên không có chứa các ký

hiệu vô ích ?

Quan hệ giữa cfl và tập hợp chính quy

ĐỊNH LÝ 6.5 :Nếu L là CFL và R là tập chính quy thì L  R là CFL.

Chứng minh

Đặt L là L(M) với PDA M (QM, , , M, q0, Z0, FM) và đặt R là L(A) với DFA A (QA, å, dA, p0, FA). Ta xây dựng PDA M’ cho L  R bằng cách cho M và A cùng “chạy song song”. Tức là với một ký hiệu nhập a thì M và A thực hiện các phép chuyển độc lập nhau. M’ chấp nhận input nếu cả M và A cùng chấp nhận.

Hình 6.6 - Chạy một FA và PDA song song

Một cách hình thức, đặt M’ (QA  QM, , , , [p0, q0], Z0, FA  FM), trong đó hàm chuyển  được xác định như sau :

 ([p, q], a, X) chứa ([p’, q’], )  dA(p, a) = p’ và dM(q, a, X) chứa (q’, ).

Chú ý rằng a có thể bằng , khi đó p’ = p.

Dễ dàng chứng minh quy nạp theo i rằng : ([p0, q0], w, Z0) ⊢iM ’ ([p, q], , )  (q0, w, Z0) ⊢iM (q, , ) và d(p0, w) = p (1)

Với i = 0: thì (1) hiển nhiên đúng vì p = p0, q = q0,  = Z0 và w = .

Giả sử (1) đúng tới i - 1 (i>0).

Xét ([p0, q0], xa, Z0) ⊢i -1M ’ ([p’, q’], a, ) ⊢M ’ ([p, q], , ) , trong đó w = xa và a là  hoặc là một ký hiệu  .

Theo giả thiết quy nạp, dA(p0, x) = p’ và (q0, x, Z0) ⊢i -1M (q’, , ).

Theo định nghĩa của d, thực tế ([p’, q’], a, ) ⊢M ‘ ([p, q], , ) nên có thể suy ra dA(p’, a) = p và (q’, a, ) ⊢M (q, , ). Vậy dA(p0, w) = p và (q0, w, Z0) ⊢*M (q, , ).

Tương tự, ta có thể chứng minh rằng : Nếu (q0, w, Z0) ⊢iM (q, , ) và dA(p0, w) = p thì ([p0, q0], w, Z0) ⊢*M ’ ([p, q], , ) (xem phần này như bài tập).

Tổng kết chương VI: Đến chương này, chúng ta đã có thể nắm bắt được một vài ý tưởng cơ bản liên quan đến các khái niệm về ngôn ngữ chính quy, ngôn ngữ phi ngữ cảnh, và mối quan hệ của chúng với các dạng ôtômát hữu hạn và đẩy xuống. Những khảo sát chứng tỏ ngôn ngữ chính quy thực sự là một tập hợp con của ngôn ngữ phi ngữ cảnh, và do đó, ôtômát đẩy xuống xét về một mặt nào đó có khả năng nhận dạng ngôn ngữ mạnh hơn rất nhiều so với ôtômát hữu hạn. Điều này gợi cho chúng ta một ý tưởng có thể mở rộng hơn nữa về khả năng đoán nhận ngôn ngữ của cơ chế ôtômát. Nếu so sánh ôtômát hữu hạn và ôtômát đẩy xuống, ta thấy rằng bản chất của sự khác biệt thể hiện ở bộ lưu trữ tạm thời dùng Stack. Nếu không có bộ lưu trữ, chúng ta có dạng ôtômát hữu hạn, nếu bộ lưu trữ là Stack, ta có dạng ôtômát đẩy xuống mạnh hơn. Từ suy luận này, chúng ta hoàn toàn có thể mong đợi để định nghĩa ngay cả những họ ngôn ngữ rộng lớn hơn nếu có thể cung cấp cho cơ chế ôtômát một bộ nhớ với khả năng lưu trữ linh hoạt hơn. Điều này dẫn đến khái niệm cơ bản về máy Turing sẽ được giới thiệu trong chương sau, một cơ chế ôtômát có tính máy móc hay tính giải thuật.

BÀI TẬP CHƯƠNG VI

6.1. Xây dựng PDA chấp nhận các ngôn ngữ :

a) {0m 1m 2n  m, n  1}

b) {ak bl cn dm  m = k + l + n}

c) {w  w  {a, b}* và #a(w) = #b(w)}

d) {w  w  {a,b}* và #a(w) = 2#b(w)}

6.2. Xây dựng PDA tương đương với văn phạm :

a) S ® + SS | *SS | a

b)S ® aS | bS | aA

A ® bB| b

B ® aC

C ® b

6.3. Xây dựng văn phạm CFG tương đương với các PDA sau :

a) M ({q0, q1}, {0, 1}, {Z0, X}, , q0, Z0, ), trong đó  được cho như sau:

d(q0, 1, Z0) = {(q0, XZ0)}

d(q0, 0, X) = {(q0, XX)}

d(q0, 1, X) = {(q1, e)}

d(q1, 1, X) = {(q1, e)}

d(q1, e, X) = {(q1, e)}

d(q1, e, Z0) = {(q1, e)}

b) M ({q0, q1}, {0, 1}, {Z0, X}, , q0, Z0, ), trong đó  được cho như sau:

d(q0, 1, Z0) = {(q0, XZ0)}

d(q0, 1, X) = {(q0, XX)}

d(q0, 0, X) = {(q1, X)}

d(q0, e, Z0) = {(q0, e)}

d(q1, 1, X) = {(q1, e)}

d(q1, 0, Z0) = {(q0, Z0)}

c) M ({q0, q1}, {a, b, c}, {Z0, X}, , q0, Z0, ), trong đó  được cho như sau:

d(q0, a, Z0) = {(q0, X)}

d(q0, a, X) = {(q0, XX)}

d(q0, c, X) = {(q1, X)}

d(q0, b, Z0) = {(q0, X)}

d(q0, b, X) = {(q0, XX)}

d(q1, c, X) = {(q1, e)}

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