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

Hình 6.1 - Mô tả một PDA

Để chấp nhận ngôn ngữ L như trên ta dùng bộ điều khiển có hai trạng thái q1, q2 và một Stack trên đó ta đặt các đĩa xanh (B), vàng (Y), đỏ (R). Thiết bị sẽ thao tác theo các quy tắc sau đây:

1) Máy sẽ bắt đầu với một đĩa đỏ ở trên Stack và bộ điều khiển ở trạng thái q1.

2) Nếu 0 được đưa vào thiết bị thì ta đặt một đĩa xanh vào Stack. Nếu đưa 1 vào thiết bị ở trạng thái q1 thì ta đặt một đĩa vàng vào Stack. Cả hai trường hợp thiết bị không thay đổi trạng thái.

3) Nếu c được đưa vào thiết bị ở trạng thái q1 thì thiết bị đổi trạng thái sang q2 và không thay đổi Stack.

4) Nếu 0 được đưa vào thiết bị ở trạng thái q2 và đỉnh Stack là đĩa màu xanh thì đĩa được lấy ra. Nếu 1 đưa vào thiết bị ở trạng thái q2 và đĩa vàng tại đỉnh Stack thì ta loại bỏ đĩa này. Trạng thái q2 không thay đổi.

5) Nếu thiết bị ở trạng thái q2 và đĩa đỏ tại đỉnh Stack ta loại bỏ đĩa này không cần ký hiệu nhập.

6) Ngoài các trường hợp trên thì thiết bị không thay đổi.

Các quy tắc trên được tóm tắt như trong bảng sau:

Hình 6.2 - Mô tả hoạt động của PDA chấp nhận ngôn ngữ {wcwR |w (0+1)*}

Một chuỗi được chấp nhận bởi thiết bị nếu nó đã đọc duyệt qua đến hết chuỗi đồng thời với Stack trở về trạng thái rỗng.

Nhận xét : Nhờ Stack có khả năng lưu giữ một số bất kỳ các ký hiệu mà PDA có thể nhớ nửa phần đầu của chuỗi (w) cho tới khi gặp ký hiệu phân cách c, cho dù chuỗi có độ dài lớn đến bao nhiêu. Và sau đó, các ký hiệu này được đem ra để so sánh dần với phần chuỗi ngược còn lại (wR). Một ôtômát hữu hạn không có được khả năng ghi nhớ đó.

Định nghĩa

Ôtômát đẩy xuống có một bộ điều khiển hữu hạn và một Stack. Stack chứa một chuỗi các ký hiệu thuộc một bộ chữ cái nào đó. Ký hiệu bên trái nhất của chuỗi xem như ký hiệu tại đỉnh Stack. PDA không đơn định nếu như có một số hữu hạn các lựa chọn phép chuyển trong mỗi lần chuyển.

Phép chuyển sẽ có hai kiểu:

- Kiểu thứ nhất phụ thuộc vào ký hiệu nhập, tức là với một trạng thái, một ký hiệu tại đỉnh Stack và một ký hiệu nhập; PDA sẽ lựa chọn trạng thái kế tiếp và một chuỗi các ký hiệu thay thế trên Stack, đầu đọc dịch đi sang phải một ký hiệu.

- Kiểu thứ hai không phụ thuộc vào ký hiệu nhập, gọi là  - dịch chuyển : tương tự như kiểu thứ nhất, chỉ ngoại trừ là ký hiệu nhập không được dùng và đầu đọc không dịch chuyển sau khi chuyển trạng thái. Thực chất, bước chuyển đặc biệt này là một sự tạm ngừng quan sát trên băng nhập để sắp xếp lại các ký hiệu trong ngăn xếp.

Có hai cách để định nghĩa ngôn ngữ chấp nhận bởi ôtômát đẩy xuống:

- Ngôn ngữ được chấp nhận bởi Stack rỗng: gồm tất cả các input mà sau một chuỗi các phép chuyển trạng thái làm cho ôtômát dẫn tới Stack rỗng.

- Ngôn ngữ được chấp nhận bởi trạng thái kết thúc: ta thiết kế một số trạng thái kết thúc, khi đó ngôn ngữ chấp nhận bởi ôtômát có thể định nghĩa gồm tất cả các input mà có một chuỗi các phép chuyển làm cho ôtômát dẫn tới một trong những trạng thái kết thúc.