Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Automat & NN hình thức] Mô phỏng máy Turing: chấp nhận, dừng hay lặp

    Mô phỏng máy Turing: chấp nhận, dừng hay lặp

    Cho một máy Turing xác định (deterministic) với ký hiệu trắng là _. Bảng chuyển gồm các luật dạng (trạng_thái, ký_hiệu_đọc) → (trạng_thái_mới, ký_hiệu_ghi, hướng) với hướng L (trái) hoặc R (phải).

    Máy bắt đầu ở trạng thái đầu, đầu đọc tại ô chỉ số 0 (ô trái nhất của băng đầu vào). Tại mỗi bước:

    • Nếu trạng thái hiện tại là trạng thái chấp nhận → dừng và ACCEPT.
    • Nếu không có luật cho (trạng_thái, ký_hiệu_đọc) → dừng (HALT).
    • Nếu đã chạy đủ L bước mà chưa chấp nhận → coi như LOOP.

    Băng vô hạn hai phía, mọi ô chưa ghi đều là _.

    Ví dụ: máy quét phải qua các ký hiệu a rồi chấp nhận khi gặp _.

    q0 a -> q0 a R
q0 _ -> acc _ R

    Với băng aaa: đọc a,a,a rồi gặp _ chuyển sang acc → ACCEPT.

    • Định dạng đầu vào:

      Dòng 1: số nguyên n — số luật chuyển. n dòng tiếp: mỗi dòng 5 token q a ns wr d (trạng thái, ký hiệu đọc, trạng thái mới, ký hiệu ghi, hướng L/R). Dòng tiếp: hai token start accept (trạng thái đầu và trạng thái chấp nhận). Dòng tiếp: số nguyên L — giới hạn số bước. Dòng cuối: chuỗi băng đầu (dùng _ cho ô trắng).

    • Ràng buộc đầu vào:

      1 ≤ n ≤ 50; 1 ≤ L ≤ 100000; độ dài băng đầu ≤ 100. Ký hiệu là một ký tự.

    • Định dạng đầu ra:

      In đúng một trong ba từ: ACCEPT, HALT, hoặc LOOP.

    Ví dụ:

    Đầu vào:

    2
q0 a q0 a R
q0 _ acc _ R
q0 acc
100
aaa

    Đầu ra:

    ACCEPT

    Giải thích:

    Quét qua 3 ô `a` (3 bước), gặp `_` chuyển sang `acc` (bước 4) → dừng chấp nhận.

    Đang tải editor...