0.4 Ôtômát đẩy xuống  (Page 3/8)

Ta có thể thấy hai cách định nghĩa cho sự chấp nhận chuỗi này là tương đương nhau trong mọi trường hợp, có nghĩa là nếu một tập hợp được chấp nhận bởi Stack rỗng của một PDA nào đó thì cũng sẽ được chấp nhận bằng trạng thái kết thúc trên một PDA khác, và ngược lại. Thiết kế PDA chấp nhận chuỗi bằng trạng thái kết thúc thường phổ biến hơn, nhưng sẽ dễ dàng hơn để chứng minh nguyên lý cơ bản của PDA khi thiết kế PDA chấp nhận chuỗi bằng Stack rỗng. Nguyên lý này được phát biểu như sau: Một ngôn ngữ được chấp nhận bởi PDA khi và chỉ khi nó là một ngôn ngữ phi ngữ cảnh.

Một cách hình thức, ta định nghĩa:

Định nghĩa : Một ôtômát đẩy xuống M là một hệ thống M (Q, , , , q0, Z0, F), trong đó :

1) Q là tập hữu hạn các trạng thái

2)  là bộ chữ cái gọi là bộ chữ cái nhập

3)  là bộ chữ cái gọi là bộ chữ cái Stack

4) : hàm chuyển ánh xạ từ Q  ( {})    tập con hữu hạn của Q  *

5) q0 là trạng thái khởi đầu

5) Z0 là một chữ cái riêng của Stack gọi là ký hiệu bắt đầu trên Stack

6) F  Q là tập các trạng thái kết thúc

(Trong trường hợp PDA được thiết kế chấp nhận ngôn ngữ bằng Stack rỗng thì tập hợp F = )

Trừ khi ta dùng các ký hiệu khác, ta quy ước dùng chữ nhỏ gần đầu bảng chữ cái để chỉ các ký hiệu nhập, các chữ nhỏ cuối bảng chữ cái để chỉ các chuỗi nhập. Các chữ hoa và chữ Hy lạp chỉ ký hiệu và chuỗi ký hiệu Stack.

Câu hỏi :

?

So sánh các thành phần trong định nghĩa hình thức cho một ôtômát đẩy xuống

PDA với ôtômát hữu hạn đã khảo sát trong chương 3 ? Nêu những khả năng mở

rộng của PDA so với FA ?

Sự dịch chuyển

Hàm chuyển phụ thuộc ký hiệu nhập :

(q, a, Z) = {(p1, 1), (p2, 2), ..., (pm, m)}

trong đó q và pi, 1  i  m, là các trạng thái thuộc tập Q, a  , Z là một ký hiệu Stack và i  *, 1  i  m, là PDA ở trạng thái q với ký hiệu nhập a và ký hiệu Z tại đỉnh Stack, nó đi vào một trạng thái pi nào đó thay Z bằng i và dịch chuyển đầu đọc đi một ký hiệu. Ta quy ước rằng ký hiệu bên trái nhất của i sẽ là ký hiệu được thay cao nhất trên Stack (nghĩa là nó nằm tại đỉnh Stack mới) và ký hiệu bên phải nhất của i là ký hiệu được thay thấp nhất trong Stack. Chú ý rằng không được phép chọn pi và j với i  j tại một bước chuyển nào đó.

Hàm chuyển không phụ thuộc ký hiệu nhập :

(q, , Z) = {(p1, 1), (p2, 2), ..., (pm, m)}

trong đó q là trạng thái mà PDA đang giữ, độc lập với ký hiệu nhập, PDA đi vào trạng thái pi thay Z bởi i với 1  i  m. Trong trường hợp này đầu đọc không dịch chuyển.

Thí dụ 6.1 :Mô tả dưới đây cho PDA chấp nhận ngôn ngữ {wcwR w  (0+1)*} bằng Stack rỗng.

M ({q1, q2}, {0, 1, c}, {R, B, Y}, d, q1, R, Æ )

1) d(q1, 0, R) = {(q1, BR)}

2)d(q1, 1, R) = {(q1, YR)}

3)d(q1, 0, B) = {(q1, BB)}

4)d(q1, 1, B) = {(q1, YB)}

5)d(q1, 0, Y) = {(q1, BY)}

6)d(q1, 1, Y) = {(q1, YY)}

7)d(q1, c, R) = {(q2, R)}

8)d(q1, c, B) = {(q2, B)}

9)d(q1, c, Y) = {(q2, Y)}

10)d(q2, 0, B) = {(q2, e)}

11)d(q2, 1, Y) = {(q2, e)}

12)d(q2, e, R) = {(q2, e)}

Hình 6.3 - Mô tả PDA chấp nhận wcwR bằng Stack rỗng

Chú ý rằng mỗi phép chuyển PDA sẽ viết lên đỉnh Stack một chuỗi  có độ dài 2. Chẳng hạn d(q1, 0, R) = {(q1, BR)}. Nếu  có độ dài bằng 1 thì PDA đơn giản là thay ký hiệu tại đỉnh Stack và không làm thay đổi độ dài Stack. Nếu  bằng  thì PDA loại bỏ (Pop) phần tử tại đỉnh Stack. Chẳng hạn d(q2, e, R) = {(q2, e)} nghĩa là PDA ở trạng thái q2 với R ở đỉnh Stack thì PDA xóa R độc lập với ký hiệu nhập, trong trường hợp này đầu đọc không dịch chuyển, điều này có nghĩa là PDA không yêu cầu còn một ký hiệu nào trên chuỗi nhập.