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] Universal TM: in cấu hình tức thời khi dừng

    Universal TM: in cấu hình tức thời khi dừng

    Máy Turing vạn năng mô phỏng máy M và có thể báo cáo cấu hình tức thời (instantaneous description) của M khi dừng.

    Mô phỏng M trên băng w (tối đa limit bước). Nếu M dừng (hết luật):

    • Dòng 1: in trạng thái dừng và số bước.
    • Dòng 2: in cấu hình băng trên đoạn có ý nghĩa (bao gồm vị trí đầu đọc), trong đó ô đang được đầu đọc trỏ tới được bọc trong dấu [ ].

    Nếu không dừng trong limit bước: in LOOP.

    Ví dụ: máy đi phải ghi X; sau khi dừng ở trạng thái q1, đầu đọc ở ô trắng cuối: dòng 2 có dạng XX[_].

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

      Dòng 1: n số luật. n dòng: q a ns wr d. Dòng tiếp: start. Dòng tiếp: số nguyên limit. Dòng cuối: chuỗi w.

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

      1 ≤ n ≤ 50; 1 ≤ limit ≤ 100000; |w| ≤ 100.

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

      Dòng 1: <trạng_thái> <số_bước>. Dòng 2: cấu hình băng với ô đầu đọc trong [ ]. Hoặc LOOP.

    Ví dụ:

    Đầu vào:

    2
q0 a q0 X R
q0 _ q1 _ R
q0
100
aa

    Đầu ra:

    q1 3
XX_[_]

    Giải thích:

    Ghi `X` tại ô 0,1 (2 bước) rồi ở ô 2 (`_`) chuyển sang q1 và sang phải (bước 3); ô 3 (`_`) không có luật của q1 → dừng. Trạng thái q1, 3 bước; băng `XX__` với đầu đọc ở ô 3: `XX_[_]`.

    Đang tải editor...