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] Phân loại: decidable / recognizable

    Phân loại: decidable / recognizable

    Trong lý thuyết tính toán, mỗi ngôn ngữ (bài toán) rơi vào một trong ba lớp:

    • D — decidable (quyết định được): tồn tại máy Turing luôn dừng và trả lời đúng.
    • RE — Turing-recognizable nhưng không decidable: có máy dừng-và-chấp-nhận cho các chuỗi thuộc ngôn ngữ, nhưng có thể lặp vô hạn với chuỗi không thuộc.
    • N — không recognizable.

    Cho tên một bài toán kinh điển, hãy in nhãn lớp của nó (D, RE, hoặc N).

    Bảng tham chiếu (một phần): A_DFA, E_DFA, EQ_DFA, A_CFG, E_CFG, ANBN, ANBNCN, PRIMES là D; A_TM, HALT_TM là RE; E_TM, EQ_TM, REGULAR_TM, COMPLEMENT_ATM là N.

    Ví dụ: A_DFA → D; HALT_TM → RE; EQ_TM → N.

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

      Một dòng: tên bài toán (một trong các mã đã liệt kê).

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

      Tên bài toán nằm trong bảng tham chiếu.

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

      D, RE, hoặc N.

    Ví dụ:

    Đầu vào:

    A_DFA

    Đầu ra:

    D

    Giải thích:

    Bài toán DFA chấp nhận w luôn quyết định được (chỉ cần mô phỏng DFA hữu hạn bước) → D.

    Đang tải editor...