Vì vậy, tôi đang nghiên cứu thử nghiệm tôi đã bật lên trên các ngôn ngữ tự động và ngôn ngữ tự do đẩy xuống và tôi bị kẹt trong cấu trúc này.Đẩy/đẩy ngăn xếp theo thứ tự ngược lại trong Tự động đẩy xuống
Tôi có mọi phần của ô tô này hoàn toàn hoạt động hoàn hảo ngoại trừ một phần mà tôi sẽ giải thích bên dưới.
Ngôn ngữ cần nhận ra là: {x # y # z # w | x, y, z, w trong {0, 1} + với x ≠ w và y ≠ z}.
Vì vậy, vấn đề tôi đang gặp là so sánh Xi với Wi, vì các yếu tố của Wi không được biết tại thời điểm automaton được xử lý W, cách mà tôi đã thiết kế.
Nếu tôi lưu trữ nội dung của X, khi thời gian đến bật và so sánh từng phần tử với W, chúng sẽ bật theo thứ tự ngược lại và do đó xem 000111 và 111000 là cùng một chuỗi và PDA sẽ từ chối , khi cần chấp nhận rõ ràng (chúng là các chuỗi khác nhau). Đây chỉ là một ví dụ, điều này cũng sẽ khiến các đầu vào khác được phân tích không chính xác.
Nếu có cách nào để đẩy nội dung của X lên ngăn xếp theo thứ tự ngược lại, chúng sẽ xuất hiện ở dạng ban đầu, cho phép tôi so sánh chính xác nội dung của chuỗi.
Nếu có cách đảo ngược nội dung của ngăn xếp sau khi đẩy bình thường, điều này cũng sẽ cho phép tôi đến giải pháp.
Mọi trợ giúp sẽ được đánh giá cao. Cảm ơn.
Tôi không hoàn toàn chắc chắn về ký hiệu của bạn. Là 'x #' bằng * lặp lại tùy ý của một số ký tự * 'x'? – dhke
@dhke nó chỉ là ký tự '#' trong chuỗi.Một ví dụ về một chuỗi trong ngôn ngữ sẽ là "01 # 01 # 10 # 10" hoặc "0 # 00 # 000 # 0000". Ngoài ra để làm rõ nếu không rõ ràng, nếu x không bằng y thì điều đó có nghĩa là x> y, x
JayB