Theo quan hệ Myhill–Nerode, hai chuỗi x, x' không phân biệt được đối với ngôn ngữ L nếu với mọi hậu tố e: x·e ∈ L ⇔ x'·e ∈ L.
Cho ngôn ngữ hữu hạn L, tập chuỗi cần xét X và tập hậu tố mở rộng E, hãy đếm số lớp phân biệt trong X: hai chuỗi cùng lớp nếu chúng cho cùng kết quả trên mọi e ∈ E.
Quy ước: dấu . biểu diễn chuỗi rỗng ε.
Ví dụ: L = {a, b}, X = {a, b, aa}, E = {.} → chữ ký = (thuộc L?): a→(T), b→(T), aa→(F) → 2 lớp.
Dòng 1: nL, rồi nL token của L. Dòng tiếp: nX, rồi nX token của X. Dòng tiếp: nE, rồi nE token của E. (. = ε).
1 ≤ nL, nX, nE ≤ 100, độ dài mỗi token ≤ 50.
Một dòng: số lớp phân biệt trong X.
Ví dụ:
Đầu vào:
2
a
b
3
a
b
aa
1
.
Đầu ra:
2
Giải thích:
Đang tải editor...