Cho một DFA đầy đủ và một chuỗi w. Hãy mô phỏng automat: bắt đầu ở trạng thái đầu, lần lượt đọc từng ký tự của w và chuyển trạng thái theo bảng chuyển. Chuỗi được chấp nhận nếu sau khi đọc hết w automat dừng ở một trạng thái chấp nhận.
Bảng chữ cái gồm k ký tự đầu tiên: a, b, c, … (chỉ số j ứng với ký tự chr(97+j)).
Ví dụ:
Input:
2 2
1 0
0 1
0
1 1
aba
Output:
REJECT
Khối mô tả DFA gồm:
n k — số trạng thái (đánh số 0..n-1) và kích thước bảng chữ cái.n dòng tiếp theo: dòng i gồm k số, số thứ j là trạng thái đích khi ở trạng thái i đọc ký tự thứ j.s.f rồi f số — tập trạng thái chấp nhận (nếu f=0 chỉ có số 0).
Sau khối DFA là một dòng chứa chuỗi w (dùng ký tự - để biểu diễn chuỗi rỗng).1 ≤ n ≤ 1000, 1 ≤ k ≤ 26, |w| ≤ 10^5. DFA đầy đủ (mọi ô bảng chuyển hợp lệ).
In ACCEPT nếu chuỗi được chấp nhận, ngược lại in REJECT.
Ví dụ:
Đầu vào:
2 2
1 0
0 1
0
1 1
aba
Đầu ra:
REJECT
Giải thích:
Đang tải editor...