Chấp nhận dữ liệu tự động đẩy xuống
Có hai cách khác nhau để xác định khả năng chấp nhận PDA.
Trạng thái cuối cùng được chấp nhận
Ở trạng thái chấp nhận cuối cùng, PDA chấp nhận một chuỗi khi, sau khi đọc toàn bộ chuỗi, PDA ở trạng thái cuối cùng. Từ trạng thái bắt đầu, chúng ta có thể thực hiện các bước di chuyển kết thúc ở trạng thái cuối cùng với bất kỳ giá trị ngăn xếp nào. Các giá trị ngăn xếp không liên quan miễn là chúng ta kết thúc ở trạng thái cuối cùng.
Đối với PDA (Q, ∑, S, δ, q 0 , I, F), ngôn ngữ được chấp nhận bởi tập các trạng thái cuối cùng F là:
L (PDA) = {w | (q 0 , w, I) ⊢ * (q, ε, x), q ∈ F}
cho bất kỳ chuỗi ngăn xếp đầu vào nào x.
Khả năng chấp nhận ngăn xếp trống
Ở đây PDA chấp nhận một chuỗi khi, sau khi đọc toàn bộ chuỗi, PDA đã làm trống ngăn xếp của nó.
Đối với PDA (Q, ∑, S, δ, q 0 , I, F), ngôn ngữ được ngăn xếp trống chấp nhận là:
L (PDA) = {w | (q 0 , w, I) ⊢ * (q, ε, ε), q ∈ Q}
Thí dụ
Xây dựng một PDA chấp nhận L = {0n 1n | n ≥ 0}
Giải pháp
Ngôn ngữ này chấp nhận L = {ε, 01, 0011, 000111, .............................}
Ở đây, trong ví dụ này, số lượng ‘a’ và ‘b’ phải giống nhau.
Ban đầu chúng tôi đặt một biểu tượng đặc biệt ‘$’ vào ngăn xếp trống.
Sau đó ở trạng thái q2, nếu chúng ta gặp đầu vào 0 và trên cùng là Null, chúng ta đẩy 0 vào ngăn xếp. Điều này có thể lặp lại. Và nếu chúng ta gặp đầu vào 1 và trên cùng là 0, chúng ta bật 0 này.
Sau đó ở trạng thái q3, nếu chúng ta gặp đầu vào 1 và đầu vào là 0, chúng ta bật giá trị này là 0. Điều này cũng có thể lặp lại. Và nếu chúng ta gặp đầu vào 1 và trên cùng là 0, chúng ta sẽ bật phần tử trên cùng.
Nếu ký hiệu đặc biệt '$' gặp ở đầu ngăn xếp, nó sẽ xuất hiện và cuối cùng nó chuyển sang trạng thái chấp nhận q 4 .
Thí dụ
Xây dựng PDA chấp nhận L = {ww R | w = (a + b) *}
Solution
Ban đầu, chúng tôi đặt một ký hiệu đặc biệt '$' vào ngăn xếp trống. Ở trạng tháiq2, các wđang được đọc. Ở trạng tháiq3, mỗi 0 hoặc 1 sẽ xuất hiện khi nó khớp với đầu vào. Nếu bất kỳ đầu vào nào khác được đưa ra, PDA sẽ chuyển sang trạng thái chết. Khi chúng ta đạt đến biểu tượng đặc biệt '$', chúng ta chuyển đến trạng thái chấp nhậnq4.