Giới thiệu về dữ liệu tự động kéo xuống
Cấu trúc cơ bản của PDA
Công cụ tự động đẩy xuống là một cách triển khai ngữ pháp không có ngữ cảnh theo cách tương tự như cách chúng tôi thiết kế DFA cho ngữ pháp thông thường. Một DFA có thể nhớ một lượng thông tin hữu hạn, nhưng một PDA có thể nhớ một lượng thông tin vô hạn.
Về cơ bản một Automaton đẩy xuống là -
"Finite state machine" + "a stack"
Một ô tô tự động đẩy xuống có ba thành phần:
- một băng đầu vào,
- một đơn vị điều khiển, và
- một ngăn xếp có kích thước vô hạn.
Đầu ngăn xếp quét ký hiệu trên cùng của ngăn xếp.
Một ngăn xếp thực hiện hai hoạt động -
Push - một biểu tượng mới được thêm vào ở trên cùng.
Pop - biểu tượng trên cùng được đọc và loại bỏ.
PDA có thể đọc hoặc không đọc một ký hiệu đầu vào, nhưng nó phải đọc phần trên cùng của ngăn xếp trong mọi quá trình chuyển đổi.
Một PDA có thể được mô tả một cách chính thức là một 7 bộ (Q, ∑, S, δ, q 0 , I, F) -
Q là số trạng thái hữu hạn
∑ là bảng chữ cái đầu vào
S là ký hiệu ngăn xếp
δ là hàm chuyển tiếp: Q × (∑ ∪ {ε}) × S × Q × S *
q0là trạng thái ban đầu (q 0 ∈ Q)
I là ký hiệu đầu ngăn xếp ban đầu (I ∈ S)
F là một tập hợp các trạng thái chấp nhận (F ∈ Q)
Biểu đồ sau đây cho thấy sự chuyển đổi trong PDA từ trạng thái q 1 sang trạng thái q 2 , được gắn nhãn là a, b → c -
Điều này có nghĩa là ở trạng thái q1, nếu chúng ta gặp một chuỗi đầu vào ‘a’ và biểu tượng trên cùng của ngăn xếp là ‘b’, sau đó chúng tôi bật ‘b’, đẩy ‘c’ ở trên cùng của ngăn xếp và chuyển sang trạng thái q2.
Các thuật ngữ liên quan đến PDA
Mô tả tức thời
Mô tả tức thời (ID) của PDA được biểu diễn bằng bộ ba (q, w, s) trong đó
q là trạng thái
w là đầu vào không tích lũy
s là nội dung ngăn xếp
Ký hiệu cửa quay
Ký hiệu "cửa quay" được sử dụng để kết nối các cặp ID đại diện cho một hoặc nhiều bước di chuyển của PDA. Quá trình chuyển đổi được biểu thị bằng ký hiệu cửa quay "⊢".
Xét một PDA (Q, ∑, S, δ, q 0 , I, F). Quá trình chuyển đổi có thể được biểu diễn toán học bằng ký hiệu cửa quay sau:
(p, aw, Tβ) ⊢ (q, w, αb)Điều này ngụ ý rằng trong khi chuyển đổi từ trạng thái p để nhà nước q, ký hiệu đầu vào ‘a’ được tiêu thụ và phần trên cùng của ngăn xếp ‘T’ được thay thế bằng một chuỗi mới ‘α’.
Note - Nếu chúng ta muốn không hoặc nhiều bước di chuyển của PDA, chúng ta phải sử dụng ký hiệu (⊢ *) cho nó.