Ngôn ngữ L = { w#w : w ∈ {0,1}* } được nhận hiệu quả bằng máy Turing hai băng: chép phần trước dấu # sang băng 2, rồi so khớp từng ký hiệu với phần sau dấu #.
Cho chuỗi s trên bảng chữ {0, 1, #}, hãy in ACCEPT nếu s có đúng một dấu #, hai nửa chỉ gồm 0/1 và bằng nhau; ngược lại REJECT.
Ví dụ: 101#101 → ACCEPT; 101#100 → REJECT; # (hai nửa rỗng) → ACCEPT.
Một dòng: chuỗi s gồm các ký tự 0, 1, #.
1 ≤ |s| ≤ 100000.
ACCEPT hoặc REJECT.
Ví dụ:
Đầu vào:
101#101
Đầu ra:
ACCEPT
Giải thích:
Đang tải editor...