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] Kiểm tra DFA nhận mọi chuỗi

    Cho một DFA đầy đủ. Ngôn ngữ của nó bằng toàn bộ Σ* (nhận mọi chuỗi) khi và chỉ khi mọi trạng thái đạt được từ trạng thái bắt đầu đều là trạng thái chấp nhận. Hãy kiểm tra.

    Bảng chữ cái gồm k ký tự đầu tiên: a, b, c, … (chỉ số j ứng với ký tự chr(97+j)).

    Ví dụ:

    Input:

    2 2
0 0
0 0
0
1 0

    Output:

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

      Khối mô tả DFA gồm:

      • Dòng 1: hai số n k — số trạng thái (đánh số 0..n-1) và kích thước bảng chữ cái.
      • n dòng tiếp theo: dòng i gồm k số, số thứ j là trạng thái đích khi ở trạng thái i đọc ký tự thứ j.
      • Dòng tiếp: trạng thái bắt đầu s.
      • Dòng cuối: f rồi f số — tập trạng thái chấp nhận (nếu f=0 chỉ có số 0).
    • Ràng buộc đầu vào:

      1 ≤ n ≤ 10^5, 1 ≤ k ≤ 26.

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

      In YES nếu L(DFA) = Σ*, ngược lại NO.

    Ví dụ:

    Đầu vào:

    2 2
0 0
0 0
0
1 0

    Đầu ra:

    YES

    Giải thích:

    Từ 0 chỉ tới 0, và 0 là trạng thái chấp nhận, nên mọi chuỗi đều được nhận → YES.

    Đang tải editor...