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

Hình thái (ID : Instantaneous Descriptions)

Để hình thức hóa cấu hình của một PDA với một PDA cụ thể, ta định nghĩa một hình thái (ID). ID phải ghi nhớ trạng thái và nội dung của Stack. ID là một bộ ba (q, w, ), trong đó q là trạng thái, w là chuỗi nhập và  là chuỗi các ký hiệu Stack.

Nếu M (Q, , , , q0, Z0, F) là một PDA, ta nói :

(q, aw, Z) ⊢M (p, w, ) nếu (q, a, Z) chứa (p, )

Lưu ý a có thể là một ký hiệu trong input hoặc . Chẳng hạn với PDA mô tả như trên, ta có (q1, BY)  d(q1, 0, Y), suy ra rằng (q1, 011, YYR) ⊢ (q1, 11, BYYR).

Ta dùng ký hiệu ⊢*M cho bao đóng phản xạ và bắt cầu của ⊢M, tức là : I ⊢* I đối với mỗi ID I, và I ⊢M J và J ⊢*M K thì I ⊢*M K. Ta viết I ⊢i K nếu ID I trở thành K sau chính xác i bước chuyển. Chữ chỉ số dưới M trong các ky 1hiệu ⊢M, ⊢iM và ⊢*M có thể được bỏ qua khi M đã được xác định.

Ngôn ngữ chấp nhận bởi PDA

Với PDA M (Q, , , , q0, Z0, F), ta định nghĩa :

Ngôn ngữ được chấp nhận bởi trạng thái kết thúc là:

L (M) = {w  (q0, w, Z0) ⊢* (p, , ) với p  F và   *}

Ngôn ngữ được chấp nhận bởi Stack rỗng là :

N(M) = {w  (q0, w, Z0) ⊢* (p, , ) với p  Q}.

Khi có sự chấp nhận bằng Stack rỗng thì tập trạng thái kết thúc là không còn cần thiết vì vậy ta ký hiệu tập trạng thái kết thúc F là .

Thí dụ 6.2 :Các phép chuyển hình thái của PDA chấp nhận chuỗi 001c100 thuộc ngôn ngữ {wcwR w  (0+1)*} bằng Stack rỗng như sau :

(q1, 001c100, R) ⊢ (q1, 01c110, YR) ⊢ (q1, 1c110, YYR) ⊢ (q1, c100, BYYR) ⊢

(q2, 100, BYYR) ⊢ (q2, 00, YYR) ⊢ (q2, 0, YR) ⊢ (q2, , R) ⊢ (q2, , ) : Chấp nhận

Nhận xét : Trong ví dụ thiết kế PDA chấp nhận ngôn ngữ {wcwR w  (0+1)*} bằng Stack rỗng như trên, ta thấy các giá trị hàm chuyển của nó luôn là là đơn trị. Tại mỗi thời điểm từ một trạng thái trong bộ điều khiển, có thể đọc vào hoặc không đọc một ký hiệu trên băng nhập, với một ký hiệu tại đỉnh Stack, chỉ có một giá trị xác định bước chuyển kế tiếp. Vì thế, ta gọi dạng PDA này là ôtômát đẩy xuống đơn định - DPDA.

PDA không đơn định (NPDA)

Thí dụ 6.3 : Thiết kế PDA chấp nhận ngôn ngữ {wwR | w  (0+1)*} bằng Stack rỗng.

Câu hỏi :

?

Hãy nêu vai trò của ký hiệu c trong ngôn ngữ được cho bởi thí dụ 6.1 và cho nhận

xét về sự khác biệt dạng chuỗi thuộc ngôn ngữ trong thí dụ 6.3 với thí dụ 6.1 đã nêu ở trên ?

Rõ ràng ta thấy khi không có sự hiện diện của ký hiệu c ở giữa chuỗi nhập để xác định thời điểm bộ điều khiển có thể chuyển từ trạng thái q1 sang trạng thái q2, thì vấn đề sẽ trở nên phức tạp hơn khi cần phải quyết định đâu là ký hiệu bắt đầu cho chuỗi ngược (wR) ? Ở mỗi thời điểm mà bộ điều khiển đọc thấy hai ký hiệu liên tiếp giống nhau trong chuỗi nhập thì bắt buộc nó phải đoán thử cả hai khả năng cho ký hiệu thứ hai: hoặc vẫn giữ trạng thái q1 và Push vào Stack nếu xem ký hiệu này vẫn thuộc chuỗi xuôi (w), hoặc chuyển sang trạng thái q2 và Pop khỏi Stack nếu xem nó là ký hiệu bắt đầu cho chuỗi ngược (wR).

Mô tả PDA không đơn định chấp nhận ngôn ngữ {wwR w  (0+1)*} bằng Stack rỗng

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

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