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] Tính độ dài bơm (pumping length) của DFA

    Theo bổ đề bơm (pumping lemma) cho ngôn ngữ chính quy, mọi ngôn ngữ được nhận bởi DFA có ppp trạng thái đều thỏa bổ đề với độ dài bơm bằng số trạng thái. Ở bài này, định nghĩa độ dài bơm của DFA là số trạng thái tới được (reachable) từ trạng thái bắt đầu — đây là cận đủ dùng được cho bổ đề bơm.

    Lý do: mọi chuỗi chấp nhận có độ dài ≥\ge≥ số trạng thái reachable đều đi qua một trạng thái lặp (nguyên lý chuồng bồ câu), cho phép "bơm" đoạn giữa.

    Hãy đếm số trạng thái tới được của DFA.

    Ví dụ: DFA có 333 trạng thái nhưng chỉ 222 tới được -> độ dài bơm 222.

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

      Dòng 1: số trạng thái QQQ (đánh số 0..Q−10..Q-10..Q−1). Dòng 2: bảng chữ cái Σ\SigmaΣ (cách nhau dấu cách). Dòng 3: trạng thái bắt đầu. Dòng 4: số trạng thái chấp nhận rồi danh sách trạng thái chấp nhận (cùng dòng). Tiếp theo Q×∣Σ∣Q\times|\Sigma|Q×∣Σ∣ dòng p a q nghĩa là δ(p,a)=q\delta(p,a)=qδ(p,a)=q (DFA đầy đủ — mọi cặp (p,a)(p,a)(p,a) có đúng một đích).

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

      1≤Q≤20001 \le Q \le 20001≤Q≤2000, 1≤∣Σ∣≤261 \le |\Sigma| \le 261≤∣Σ∣≤26.

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

      In một số nguyên: độ dài bơm (số trạng thái tới được từ trạng thái bắt đầu).

    Ví dụ:

    Đầu vào:

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

    Đầu ra:

    2

    Giải thích:

    Từ 0 tới được {0,1}; trạng thái 2 không tới được. Độ dài bơm = 2.

    Đang tải editor...