Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Trình biên dịch] Tối tiểu hoá DFA

    Sau khi xác định hoá NFA thành DFA, một động cơ regex hiệu năng cao thường tiếp tục tối tiểu hoá DFA để giảm số trạng thái cần lưu trữ mà vẫn nhận diện đúng ngôn ngữ.

    Cho một DFA đầy đủ (complete): nnn trạng thái 0..n−10..n-10..n−1, bảng chữ cái Σ\SigmaΣ gồm các ký hiệu cho trước, hàm chuyển δ(i,c)\delta(i, c)δ(i,c) xác định với mọi trạng thái iii và mọi ký hiệu c∈Σc \in \Sigmac∈Σ, một trạng thái đầu, và một tập trạng thái kết thúc.

    Hãy tính số trạng thái của DFA tối tiểu tương đương, thu được bằng cách:

    1. Loại bỏ các trạng thái không thể đến được (unreachable) từ trạng thái đầu.
    2. Gộp các trạng thái tương đương: hai trạng thái u,vu, vu,v (còn lại sau bước 1) được gọi là tương đương nếu và chỉ nếu chúng cùng là trạng thái kết thúc hoặc cùng không phải trạng thái kết thúc, và với mọi ký hiệu c∈Σc \in \Sigmac∈Σ, δ(u,c)\delta(u,c)δ(u,c) và δ(v,c)\delta(v,c)δ(v,c) cũng tương đương với nhau (định nghĩa đệ quy, tính bằng thuật toán tinh chỉnh phân hoạch — partition refinement — kiểu Moore cho tới khi ổn định).
    • Định dạng đầu vào:
      • Dòng 1: hai số nguyên nnn và ∣Σ∣|\Sigma|∣Σ∣ (1≤n≤2001 \le n \le 2001≤n≤200, 1≤∣Σ∣≤261 \le |\Sigma| \le 261≤∣Σ∣≤26).
      • Dòng 2: ∣Σ∣|\Sigma|∣Σ∣ ký hiệu (mỗi ký hiệu là một chữ cái thường, đôi một phân biệt), cách nhau bởi dấu cách — thứ tự liệt kê này xác định thứ tự cột của bảng chuyển ở các dòng tiếp theo.
      • nnn dòng tiếp theo: dòng thứ iii (tính từ 000) gồm ∣Σ∣|\Sigma|∣Σ∣ số nguyên là δ(i,c1),δ(i,c2),…,δ(i,c∣Σ∣)\delta(i, c_1), \delta(i, c_2), \dots, \delta(i, c_{|\Sigma|})δ(i,c1​),δ(i,c2​),…,δ(i,c∣Σ∣​) theo đúng thứ tự ký hiệu ở dòng 2.
      • Dòng tiếp theo: trạng thái đầu.
      • Dòng tiếp theo: số nguyên kkk — số trạng thái kết thúc.
      • Dòng tiếp theo: kkk số nguyên là các trạng thái kết thúc, cách nhau bởi dấu cách (dòng rỗng nếu k=0k=0k=0).
    • Định dạng đầu ra:

      In ra một số nguyên duy nhất — số trạng thái của DFA tối tiểu tương đương.

    Ví dụ:

    Đầu vào:

    6 2
a b
1 2
0 3
4 5
4 5
4 5
5 5
0
3
2 3 4

    Đầu ra:

    3

    Đầu vào:

    7 2
a b
1 2
0 3
4 5
4 5
4 5
5 5
6 6
0
3
2 3 4

    Đầu ra:

    3

    Đang tải editor...