Ngôn ngữ L = { aⁿbⁿ : n ≥ 0 } không chính quy nhưng được nhận bởi một máy Turing (và cả PDA). Máy Turing hoạt động: lặp lại việc gạch bỏ (đánh dấu) chữ a ngoài cùng bên trái và chữ b ngoài cùng bên phải cho tới khi hết; nếu còn dư a hoặc b thì từ chối.
Cho chuỗi s trên bảng chữ {a, b}, hãy in ACCEPT nếu s ∈ L, ngược lại REJECT. Chuỗi rỗng thuộc L (ứng với n = 0).
Ví dụ: aabb → ACCEPT; aab → REJECT; ab → ACCEPT.
Một dòng: chuỗi s (có thể rỗng), chỉ gồm ký tự a và b.
0 ≤ |s| ≤ 100000; s chỉ gồm a, b.
ACCEPT hoặc REJECT.
Ví dụ:
Đầu vào:
aabb
Đầu ra:
ACCEPT
Giải thích:
Đang tải editor...