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 số lần xuất hiện của số 0 và số 3 sẽ bằng nhau và số lần xuất hiện của số 1 và 2 sẽ bằng nhau và số lần xuất hiện của tất cả các số phải nhỏ nhất là 1, điều này 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à một bộ 7 (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 n 3 n - 03, 0033, 000333, v.v. Số 0 bằng không. trong 3 giây. Khi m bằng 0, chúng ta sẽ không có 1s và 2s. Tiếp tục đẩy các số 0 và ngay sau khi gặp 3 đầ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 m 2 m - 12, 1122, 111222, v.v. Số 1 bằng không. trong 2 giây. Khi n bằng 0, chúng ta sẽ không có số 0 và 3 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 2 m 3 n - 0123, 001233, 011223, v.v. Số 0 bằng không. của 3s và 1s bằng 2s. Tiếp tục đẩy các số 0 và 1. Ngay sau khi gặp 2 đầu tiên, sau đó bật 1s nếu nó ở trên cùng và sau đó bật 0s cho phần còn lại của 3s. Nếu chúng ta đến cuối và không còn số 0 thì chuỗi được chấp nhận.
-
Chuỗi NULL cũng được chấp nhận. 0 0 1 0 2 0 3 0 .
Hãy hiểu máy
-
Chuyển đổi cho trạng thái q0 -
-
(0, I / 0, I) - 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 / 0,0) - 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 khi tiếp theo là 1 hoặc 3.
-
(1, 0 / 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ì đẩy 1 lên đầu ngăn xếp và di chuyển đến q1. Ngăn xếp trở thành 10 ...
-
(1, I / 1, I) - 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ì nhấn 1 và di chuyển đến q5.
-
(3, 0 / e) - Nếu đỉnh của ngăn xếp là 0 và ký hiệu đầu vào hiện tại là 3 thì bật 0 và di chuyển đến q3.
-
($, I / I) - Nếu đỉnh 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 q4. Đối với chuỗi NULL.
-
-
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 khi tiếp theo là 2.
-
(2, 1 / e) - 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 / e) - 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.
-
(3, 0 / e) - Nếu đỉnh của ngăn xếp là 0 và ký hiệu đầu vào hiện tại là 3 thì bật 0 và di chuyển đến q3.
-
-
Chuyển đổi cho trạng thái q3 -
-
(3, 0 / e) - Nếu đỉnh của ngăn xếp là 0 và ký hiệu đầu vào hiện tại là 3 thì bật 1 và giữ nguyên ở q3.
-
($, I / I) - Nếu đỉnh 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 q4. Đối với chuỗi NULL.
-
-
Chuyển đổi cho trạng thái q5 -
-
(1, 1 / 1,1) - 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 ở q5. Ngăn xếp trở thành 11 .... Tiếp tục đẩy 1 giây cho đến khi tiếp theo là 2.
-
(2, 1 / e) - 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 q6.
-
-
Chuyển đổi cho trạng thái q6 -
-
(2, 1 / e) - 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 ở q6.
-
($, I / I) - Nếu đỉnh 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 q4. Đối với chuỗi NULL.
-