Chúng tôi được cung cấp một ngôn ngữ “L” và nhiệm vụ là tạo 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 ký tự 'a' phải tăng gấp đôi thời gian xuất hiện của ký tự 'b' và số lần xuất hiện của ký tự 'c' phải gấp bốn lần số lần của 'd' và số lần xuất hiện của tất cả các ký tự phải là tối thiểu 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 -
-
c 4n d n - ccccd, ccccccccdd, v.v. Số cs gấp 4 lần số không. của ds. Khi m là 0, chúng ta sẽ không có as và bs. Tiếp tục đẩy cs và ngay khi gặp d đầu tiên, sau đó bật 4 c khỏi ngăn xếp. Nếu chúng ta đến cuối chuỗi và không còn cs thì chuỗi đó được chấp nhận.
-
một 2m b m - aab, aaaabb, v.v. Số tương tự là 2 lần so với số không. của bs. Khi n bằng 0, chúng ta sẽ không có cs và ds. Tiếp tục đẩy ngay khi gặp b đầu tiên rồi bật 2 b ra khỏi ngăn xếp. Nếu chúng ta đến cuối chuỗi và không có giá trị thì chuỗi đó được chấp nhận.
-
một 2m c 4n d n b m - aaccccdb, aaaaccccccccddbb. Số như là 2 lần so với không. của bs và cs bằng 4 lần số ds. Tiếp tục đẩy như và cs. Ngay khi bắt gặp chữ d đầu tiên, sau đó bật 4 cs nếu nó ở trên cùng và sau đó bật 2 như đối với phần còn lại của bs. Nếu chúng ta đến cuối và không còn a thì chuỗi được chấp nhận.
-
Chuỗi NULL cũng được chấp nhận. a 0 c 0 d 0 b 0 .
Hãy hiểu máy
-
Chuyển đổi cho trạng thái q0 -
-
(a, I / a, I) - Nếu đỉnh của ngăn xếp là I và ký hiệu đầu vào hiện tại là a thì đẩy a lên đầu ngăn xếp và giữ nguyên ở q0. Ngăn xếp trở thành một…
-
(c, I / c, I) - Nếu đỉnh của ngăn xếp là I và ký hiệu đầu vào hiện tại là c thì đẩy c lên trên cùng của ngăn xếp và giữ nguyên ở q0. Ngăn xếp trở thành cI ...
-
(a, a / a, a) - Nếu đỉnh của ngăn xếp là a và ký hiệu đầu vào hiện tại cũng là a thì đẩy a lên đầu ngăn xếp và giữ nguyên ở q0. Ngăn xếp trở thành aa .... Tiếp tục đẩy cho đến khi tiếp theo là c hoặc b.
-
(c, c / c, c) - Nếu đỉnh của ngăn xếp là c và ký hiệu đầu vào hiện tại cũng là c thì đẩy c lên đỉnh của ngăn xếp và giữ nguyên ở q0. Ngăn xếp trở thành cc .... Tiếp tục đẩy cs cho đến khi tiếp theo là d.
-
(b, a / e, aa) - Nếu đỉnh của ngăn xếp là a và ký hiệu đầu vào hiện tại là b thì bật 2 khi từ ngăn xếp và di chuyển đến q3.
-
(c, a / c, a) - Nếu đỉnh của ngăn xếp là a và ký hiệu đầu vào hiện tại là c thì đẩy c lên trên cùng của ngăn xếp và di chuyển đến q1. Ngăn xếp trở thành ca ...
-
(d, c / e, cccc) - Nếu đỉnh của ngăn xếp là c và ký hiệu đầu vào hiện tại là d thì bật 4 ds từ ngăn xếp và di chuyển đến q4.
-
($, I / 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à di chuyển đến q5. Đối với chuỗi NULL.
-
-
Chuyển đổi cho trạng thái q1 -
-
(c, c / c, c) - Nếu đỉnh của ngăn xếp là c và ký hiệu đầu vào hiện tại cũng là c thì đẩy c lên trên cùng của ngăn xếp và giữ nguyên ở q1. Ngăn xếp trở thành cc .... Tiếp tục đẩy cs cho đến khi tiếp theo là d.
-
(d, c / e, cccc) - Nếu đỉnh của ngăn xếp là c và ký hiệu đầu vào hiện tại là d thì bật 4 d từ ngăn xếp và di chuyển đến q2.
-
-
Chuyển đổi cho trạng thái q2 -
-
(d, c / e, cccc) - Nếu đỉnh của ngăn xếp là c và ký hiệu đầu vào hiện tại là d thì bật 4 d từ ngăn xếp và di chuyển đến q2.
-
(b, a / e, aa) - Nếu đỉnh của ngăn xếp là a và ký hiệu đầu vào hiện tại là b thì bật 2 khi từ ngăn xếp và di chuyển đến q3.
-
-
Chuyển đổi cho trạng thái q3 -
-
(b, a / e, aa) - Nếu đỉnh của ngăn xếp là a và ký hiệu đầu vào hiện tại là b thì bật 2 như từ ngăn xếp và vẫn ở q3.
-
($, I / 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à di chuyển đến q5. Đối với chuỗi NULL.
-
-
Chuyển đổi cho trạng thái q4 -
-
(d, c / e, cccc) - Nếu đỉnh của ngăn xếp là c và ký hiệu đầu vào hiện tại là d thì bật 4 ds từ ngăn xếp và giữ nguyên ở q4.
-
($, I / 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à di chuyển đến q5. Đối với chuỗi NULL.
-