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 ngôn ngữ của DFA có rỗng không

    Cho DFA M=(Q,Σ,δ,q0,F)M=(Q,\Sigma,\delta,q_0,F)M=(Q,Σ,δ,q0​,F). Xác định ngôn ngữ L(M)L(M)L(M) có rỗng hay không.

    L(M)=∅L(M)=\varnothingL(M)=∅ khi và chỉ khi không có trạng thái chấp nhận nào tới được (reachable) từ q0q_0q0​.

    Thuật toán: BFS/DFS từ q0q_0q0​, kiểm tra có gặp trạng thái thuộc FFF không.

    Ví dụ: nếu mọi đường đi từ q0q_0q0​ đều không chạm FFF thì ngôn ngữ rỗng.

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

      Dòng 1: số nguyên QQQ — số trạng thái (đánh số 0..Q−10..Q-10..Q−1). Dòng 2: các ký tự bảng chữ cái Σ\SigmaΣ, phân tách bởi dấu cách. Dòng 3: trạng thái bắt đầu q0q_0q0​. Dòng 4: số trạng thái chấp nhận FFF rồi danh sách các trạng thái chấp nhận (cùng dòng, cách nhau dấu cách). Tiếp theo Q×∣Σ∣Q\times|\Sigma|Q×∣Σ∣ dòng, mỗi dòng p a q nghĩa là δ(p,a)=q\delta(p,a)=qδ(p,a)=q.

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

      1≤Q≤10001 \le Q \le 10001≤Q≤1000, 1≤∣Σ∣≤261 \le |\Sigma| \le 261≤∣Σ∣≤26.

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

      In EMPTY nếu L(M)=∅L(M)=\varnothingL(M)=∅, ngược lại in NONEMPTY.

    Ví dụ:

    Đầu vào:

    3
0 1
0
1 2
0 0 0
0 1 1
1 0 1
1 1 1
2 0 2
2 1 2

    Đầu ra:

    EMPTY

    Giải thích:

    Từ 0 chỉ tới được {0,1}, không chạm F={2}. Vậy ngôn ngữ rỗng -> EMPTY.

    Đang tải editor...