Chúng tôi được cung cấp một ngôn ngữ “L” và nhiệm vụ là xây dựng một dữ liệu tự động kéo xuống cho ngôn ngữ đã cho, giải thích rằng các lần xuất hiện của 1 sẽ là sự bổ sung các lần xuất hiện của 0 và 2 và ngoài ra, sự xuất hiện của 0 và 2 sẽ là mức tối thiểu cũng có thể làm cho chuỗi NULL và nó phải được tự động chấp nhận.
Dữ liệu tự động kéo xuống là gì?
Tự động dữ liệu đẩy xuống hoặc tự động hóa đẩy xuống hoặc PDA là một kỹ thuật để triển khai ngữ pháp không có văn bản theo cách tương tự mà chúng tôi thiết kế Tự động hóa hữu hạn xác định hoặc DFA cho một ngữ pháp thông thường. DFA có thể hoạt động trên dữ liệu hữu hạn, nhưng PDA có thể hoạt động trên dữ liệu vô hạn. Chúng ta có thể hiểu dữ liệu tự động kéo xuống là sự kết hợp của “máy tiểu bang hữu hạn” và “ngăn xếp”.
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à
-
ngăn xếp có kích thước vô hạn.
Một PDA có thể được mô tả một cách chính thức là 7 bộ (Q, Σ, S, δ, q0, 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 *
-
q0 là trạng thái ban đầu (q0 Ε Q)
-
I là ký hiệu đầu ngăn xếp ban đầu (I Ε S)
-
F là tập hợp các trạng thái chấp nhận (F Ε Q)
Hãy xây dựng một Dữ liệu tự động kéo xuống cho ngôn ngữ nhất định -
Các chuỗi được PDA này chấp nhận có dạng -
-
0 m 1 m - 01, 0011, 000111, v.v. Số 0 bằng không. trong 1 giây. Khi n bằng 0, chúng ta sẽ không có số 2 nào. Tiếp tục đẩy các số 0 và ngay khi gặp số 1 đầu tiên sau đó bật các số 0. Nếu chúng ta đến cuối chuỗi và không còn số 0 thì chuỗi đó được chấp nhận.
-
1 n 2 n - 12, 1122, 111222, v.v. Số 1 bằng không. trong 2 giây. Khi m bằng 0, chúng ta sẽ không có số 0 nào. Tiếp tục đẩy 1s và ngay sau khi chạm vào 2 đầu tiên sau đó bật 1s. Nếu chúng ta đến cuối chuỗi và không còn 1 giây nào thì chuỗi đó được chấp nhận.
-
0 n 1 m + n 2 m - 0112, 001112, 001112, v.v. Số 1 bằng tổng của không. 0s và 2s. Tiếp tục đẩy các số 0 ngay khi gặp số 1 đầu tiên sau đó bật các số 0 cho đến khi không còn số 0 nào. Bây giờ một lần nữa đẩy 1s cho đến khi gặp 2 đầu tiên. Sau đó, cứ mỗi 2 bắt đầu bật 1s cho đến khi chúng ta không còn 1s nào. Nếu chúng ta đi đến cuối và không còn 1 thì chuỗi được chấp nhận.
-
Chuỗi NULL cũng được chấp nhận. 0 0 1 0 2 0
Hãy hiểu máy
-
Chuyển đổi cho trạng thái q0 -
-
(0, I / 0I) - Nếu đỉnh của ngăn xếp là I và ký hiệu đầu vào hiện tại là 0 thì đẩy 0 lên đầu ngăn xếp và giữ nguyên ở q0. Ngăn xếp trở thành 0I ...
-
(0, 0/00) - Nếu đỉnh của ngăn xếp là 0 và ký hiệu đầu vào hiện tại cũng là 0 thì đẩy 0 lên trên cùng của ngăn xếp và giữ nguyên ở q0. Ngăn xếp trở thành 00 .... Tiếp tục đẩy các số 0 cho đến 1 hoặc 2 tiếp theo
-
(1, I / 1I) - Nếu đỉnh của ngăn xếp là I và ký hiệu đầu vào hiện tại là 1 thì đẩy 1 lên đầu ngăn xếp và di chuyển đến q1. Ngăn xếp trở thành 1I ...
-
(1, 0 / $) - Nếu đỉnh của ngăn xếp là 0 và ký hiệu đầu vào hiện tại là 1 thì bật 0 và di chuyển đến q1.
-
(1, 0 / $) - Nếu đỉnh của ngăn xếp là 0 và ký hiệu đầu vào hiện tại là 1 thì bật 0 và di chuyển đến q1.
-
-
Chuyển đổi cho trạng thái q1 -
-
(1, 1/11) - Nếu đỉnh của ngăn xếp là 1 và ký hiệu đầu vào hiện tại cũng là 1 thì đẩy 1 lên đầu ngăn xếp và giữ nguyên ở q1. Ngăn xếp trở thành 11 .... Tiếp tục đẩy 1 giây cho đến 0 hoặc 2 tiếp theo
-
(1, 0 / $) - Nếu đỉnh của ngăn xếp là 0 và ký hiệu đầu vào hiện tại là 1 thì bật 0 và giữ nguyên ở q1.
-
($, I / I) - Nếu trên cùng của ngăn xếp là I và không có đầu vào thì không làm gì cả và chuyển đến qf.
-
(2, 1 / $) - Nếu đỉnh của ngăn xếp là 1 và ký hiệu đầu vào hiện tại là 2 thì bật 1 và di chuyển đến q2.
-
-
Chuyển đổi cho trạng thái q2 -
-
(2, 1 / $) - Nếu đỉnh của ngăn xếp là 1 và ký hiệu đầu vào hiện tại là 2 thì bật 1 và giữ nguyên ở q2.
-
($, I / I) - Nếu trên cùng của ngăn xếp là I và không có đầu vào thì không làm gì cả và chuyển sang qf.
-