Một động cơ regex dựa trên DFA xử lý chuỗi đầu vào từng ký tự một theo bảng chuyển trạng thái δ. Khác với mô hình DFA hoàn chỉnh lý thuyết (luôn có chuyển cho mọi ký hiệu, kể cả về một trạng thái bẫy), bảng chuyển ở đây có thể không đầy đủ: nếu tại một bước nào đó không tồn tại δ(p,c), động cơ phải dừng lại ngay lập tức và báo vị trí gặp lỗi, thay vì ngầm định chuyển sang trạng thái lỗi.
Cho một DFA (không nhất thiết hoàn chỉnh) với n trạng thái đánh số từ 0 đến n−1, trạng thái bắt đầu s, t chuyển trạng thái tường minh δ(p,c)=q, và f trạng thái kết thúc. Cho một chuỗi w (có thể rỗng), hãy mô phỏng việc xử lý w theo DFA này, từng ký tự một, từ trái sang phải.
Ví dụ: DFA có n=2 trạng thái, chuyển δ(0,a)=1, δ(1,a)=0, trạng thái kết thúc {0}, bắt đầu từ 0. Với w= aa: bước 1 (đọc ký tự a đầu) đưa về trạng thái 1; bước 2 (đọc ký tự a thứ hai) đưa về trạng thái 0. Đọc hết chuỗi, trạng thái cuối là 0 — thuộc tập kết thúc, nên kết quả là chấp nhận.
Dòng 1: bốn số nguyên n, t, f, s — lần lượt là số trạng thái, số chuyển tường minh, số trạng thái kết thúc, và trạng thái bắt đầu.
t dòng tiếp theo, mỗi dòng ba giá trị p, c, q (nghĩa là δ(p,c)=q; c là một ký tự). Không có cặp (p,c) nào lặp lại.
Dòng tiếp theo gồm f số nguyên là các trạng thái kết thúc, cách nhau khoảng trắng (nếu f=0 đây là dòng rỗng).
Dòng cuối cùng là chuỗi w cần xử lý (có thể là dòng rỗng nếu w là chuỗi rỗng).
Nếu trong quá trình đọc w từ trái sang phải, khi đang ở trạng thái p và gặp ký tự thứ i của w (đánh số từ 1) mà không tồn tại δ(p,wi), in ra đúng một dòng theo định dạng STUCK p i rồi dừng ngay, không xử lý các ký tự còn lại.
Nếu đọc hết w mà không bị kẹt ở bước nào, in ra ACCEPT nếu trạng thái đạt được sau cùng thuộc tập trạng thái kết thúc, ngược lại in ra REJECT.
Với ví dụ ở trên, kết quả in ra là:
ACCEPT
Ví dụ:
Đầu vào:
2 2 1 0
0 a 1
1 a 0
0
aa
Đầu ra:
ACCEPT
Đầu vào:
2 1 1 0
0 a 1
0
ab
Đầu ra:
STUCK 1 2
Đang tải editor...