Mọi ngôn ngữ hữu hạn L chính quy nên có hữu hạn lớp Myhill–Nerode. Lớp của chuỗi x xác định bởi ngôn ngữ dư L/x = { y : xy ∈ L }. Số lớp = số ngôn ngữ dư khác nhau khi x chạy trên Σ*, gồm cả lớp chết (dư rỗng, ứng với các x không là tiền tố của từ nào).
Cho bảng chữ và các từ của L (dùng . cho từ rỗng), hãy in số lớp Myhill–Nerode = (số ngôn ngữ dư khác nhau trên các tiền tố) + 1 (lớp chết).
Ví dụ: Σ = ab, L = {a} → dư của ε là {a}, dư của a là {ε}, cộng lớp chết → 3.
Dòng 1: bảng chữ (chuỗi các ký hiệu). Dòng 2: n. n dòng: các từ của L (. = từ rỗng).
1 ≤ |Σ| ≤ 26, 0 ≤ n ≤ 100 (n có thể 0: ngôn ngữ rỗng), độ dài từ ≤ 50.
Một dòng: số lớp Myhill–Nerode.
Ví dụ:
Đầu vào:
ab
1
a
Đầu ra:
3
Giải thích:
Đang tải editor...