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 DFA trên một chuỗi

    Cho một ô-tô-mát hữu hạn đơn định (DFA) M=(Q,Σ,δ,q0,F)M=(Q,\Sigma,\delta,q_0,F)M=(Q,Σ,δ,q0​,F) và một chuỗi www. Hãy xác định MMM có chấp nhận www hay không.

    DFA chấp nhận www nếu khi xuất phát từ q0q_0q0​ và đọc lần lượt các ký tự của www theo δ\deltaδ, trạng thái cuối nằm trong tập chấp nhận FFF. Nếu gặp bước chuyển không xác định thì coi như không chấp nhận.

    Ví dụ: DFA chấp nhận chuỗi nhị phân có số chữ số 111 chẵn; với w=11w=11w=11 kết quả là YES.

    • Đị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. Dòng cuối: chuỗi www cần kiểm tra (có thể rỗng — khi đó là dòng trống).

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

      1≤Q≤1001 \le Q \le 1001≤Q≤100, 1≤∣Σ∣≤261 \le |\Sigma| \le 261≤∣Σ∣≤26, 0≤∣w∣≤1050 \le |w| \le 10^50≤∣w∣≤105.

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

      In YES nếu DFA chấp nhận www, ngược lại in NO.

    Ví dụ:

    Đầu vào:

    2
0 1
0
1 0
0 0 0
0 1 1
1 0 1
1 1 0
11

    Đầu ra:

    YES

    Giải thích:

    DFA đếm chẵn/lẻ số ký tự 1. Đọc '11': 0->1->0. Trạng thái cuối 0 thuộc F={0} nên chấp nhận -> YES.

    Đang tải editor...