Số lớp tương đương Myhill–Nerode của một ngôn ngữ chính quy bằng số trạng thái của DFA tối tiểu nhận diện nó (chỉ tính phần đạt tới được từ trạng thái đầu).
Cho một DFA trên {0,1}, hãy in số lớp Myhill–Nerode = số trạng thái của DFA tối tiểu tương đương. Thuật toán: (1) loại trạng thái không đạt tới; (2) phân hoạch theo nhận/không nhận rồi tinh chỉnh theo hàm chuyển (Moore).
Ví dụ: DFA đếm số '1' theo modulo 3 (3 trạng thái đều đạt tới, phân biệt được) → 3 lớp.
Dòng 1: n. n dòng: d0 d1. Dòng tiếp: trạng thái đầu. Dòng tiếp: các trạng thái nhận (có thể trống).
1 ≤ n ≤ 200.
Một dòng: số lớp Myhill–Nerode.
Ví dụ:
Đầu vào:
3
0 1
1 2
2 0
0
0
Đầu ra:
3
Giải thích:
Đang tải editor...