solution

Cho một biểu thức chính quy $R$ trên bảng chữ cái $\{0,1\}$, với cú pháp giống hai bài toán trước (ký hiệu đơn 0, 1; ký hiệu đặc biệt @ cho ngôn ngữ $\{\varepsilon\}$ và # cho ngôn ngữ rỗng $\emptyset$; phép nối liền kề; phép hợp |; các toán tử hậu tố *, +, ?; dấu ngoặc đơn ( ) để nhóm), hãy thực hiện đầy đủ quy trình sau của một động cơ regex hoàn chỉnh:

1. Xây dựng NFA bằng Thompson construction.
2. Xác định hoá bằng subset construction để có DFA hoàn chỉnh trên bảng chữ cái $\{0,1\}$ — nghĩa là mọi trạng thái đều có đúng một chuyển cho ký hiệu 0 và đúng một chuyển cho ký hiệu 1; nếu một trạng thái DFA (tập con trạng thái NFA) không có chuyển hợp lệ với một ký hiệu nào đó, chuyển nó tới một trạng thái bẫy chung (không chấp nhận, tự lặp lại chính nó với mọi ký hiệu).
3. Tối tiểu hoá DFA hoàn chỉnh đó bằng thuật toán làm mịn phân hoạch (partition refinement, còn gọi là thuật toán Moore): khởi tạo phân hoạch thành hai khối (trạng thái kết thúc / không kết thúc), rồi lặp lại việc tách một khối thành các khối con nếu các trạng thái trong khối đó có chuyển tới các khối khác nhau (theo cùng ký hiệu), cho đến khi phân hoạch ổn định.

Cho biết số trạng thái của DFA tối tiểu (bằng số khối trong phân hoạch ổn định cuối cùng).

Ví dụ (kinh điển trong lý thuyết automat): $R =$ (0|1)*011 — ngôn ngữ các chuỗi nhị phân kết thúc bằng 011 — có DFA tối tiểu gồm đúng $4$ trạng thái.