solution

Aho và Ullman đề xuất chiến lược phục hồi lỗi toàn cục (global error correction): khi chuỗi ký hiệu đầu vào không hợp lệ, tìm chuỗi hợp lệ (gần nhất theo khoảng cách chỉnh sửa) mà ngôn ngữ chấp nhận, thay vì chỉ sửa cục bộ.

Cho một ô-tô-mát hữu hạn đơn định đầy đủ (DFA) $M = (Q, \Sigma, \delta, q_0, F)$ với $|Q|=k$ trạng thái (đánh số $0..k-1$), bảng chuyển $\delta$ đầy đủ (mọi cặp trạng thái–ký hiệu đều xác định), trạng thái đầu $q_0$, tập trạng thái chấp nhận $F \ne \emptyset$. Cho một chuỗi $s$ trên $\Sigma$ (có thể không được $M$ chấp nhận).

Định nghĩa 3 phép chỉnh sửa, mỗi phép chi phí $1$: chèn 1 ký hiệu, xoá 1 ký hiệu, thay 1 ký hiệu bằng ký hiệu khác. Hãy tìm chi phí nhỏ nhất để biến $s$ thành một chuỗi $s'$ được $M$ chấp nhận (tức đưa $M$ từ $q_0$ đến một trạng thái thuộc $F$ khi đọc $s'$). Nếu $s$ đã được chấp nhận, chi phí là $0$.

Ví dụ: $\Sigma=\{a,b\}$, 2 trạng thái $\{0,1\}$, $q_0=0$, $F=\{1\}$, $\delta(q,a)=1$ và $\delta(q,b)=0$ với mọi $q$ (tức $M$ chấp nhận đúng các chuỗi không rỗng có ký tự cuối là a). Với $s=$ bb: thay ký tự cuối b thành a được ba, được chấp nhận, chi phí $1$ — đây là chi phí nhỏ nhất có thể.