Chuyển biểu thức chính quy thành ôtômat

Ta sẽ xem cách chuyển một biểu thức chính quy bất kì thành ôtômat hữu hạn không đơn định.

Ví dụ

Trước khi mô tả thuật toán, ta xem qua một ví dụ để thấy mục tiêu là gì. Cho biểu thức chính quy a(b|c)x^∗. Bằng lời, ngôn ngữ mà biểu thức chính quy này biểu diễn gồm các xâu bắt đầu bằng chữ “a”, tiếp theo là chữ “b” hoặc chữ “c”, rồi đến chữ “x” lặp lại số lần tuỳ ý. Có xây dựng được ôtômat đoán nhận ngôn ngữ này không? Có chứ, hãy xem:

Rõ ràng ôtômat này đoán nhận đúng ngôn ngữ đó. Câu hỏi đặt ra là với mọi biểu thức chính quy, có tồn tại ôtômat đoán nhận ngôn ngữ tương ứng không. Câu trả lời là có.

Mô tả thuật toán chuyển biểu thức chính quy thành ôtômat

Giả sử đầu vào là biểu thức chính quy R. Từ bài về biểu thức chính quy, ta biết biểu thức chính quy có tất cả sáu dạng. Vì vậy, ta phân biệt sáu trường hợp:

1. R = a với một kí hiệu a ∈ Σ nào đó. Tức là biểu thức chính quy chỉ là một kí hiệu của bảng chữ cái Σ đang xét. Ôtômat đoán nhận một kí hiệu a như sau:

   

2. R = ϵ, xâu rỗng. Ôtômat đoán nhận xâu rỗng như sau:

   

3. R = ∅, biểu thức chính quy biểu diễn ngôn ngữ rỗng. Ôtômat đoán nhận ngôn ngữ này là:

   

4. R = R₁ ∪ R₂, trong đó R₁, R₂ là biểu thức chính quy. Ta đã biết hợp của hai ngôn ngữ chính quy là ngôn ngữ chính quy và ta xây dựng được ôtômat đoán nhận ngôn ngữ đó. Nói cách khác, giả sử ta có các ôtômat đoán nhận ngôn ngữ biểu diễn bởi các biểu thức R₁ và R₂; từ chúng, ta xây dựng ôtômat đoán nhận ngôn ngữ biểu diễn bởi biểu thức R₁ ∪ R₂. Ví dụ: nếu R₁ = a và R₂ = ϵ, theo cách làm đó ta được ôtômat sau:

   

5. R = R₁ ∘ R₂, trong đó R₁, R₂ là biểu thức chính quy. Tương tự trường hợp trên. Phép ghép hai ngôn ngữ chính quy cho một ngôn ngữ chính quy, nên ta xây dựng được ôtômat đoán nhận ngôn ngữ đó. Chẳng hạn, nếu R₁ = a, R₂ = b thì phép ghép như sau:

   

6. $R=(R_1^{\ast })$, trong đó R₁ là biểu thức chính quy. Ta cũng đã biết bao đóng của ngôn ngữ chính quy là ngôn ngữ chính quy. Chẳng hạn, nếu R = a^∗ thì ôtômat như sau:

   

Áp dụng lần lượt các bước này, ta chuyển toàn bộ biểu thức chính quy thành ôtômat hữu hạn.

Ví dụ hoàn chỉnh

Thử chuyển biểu thức chính quy (a|bc)^∗. Ta lần lượt được các ôtômat sau:

Ôtômat thu được cuối cùng đoán nhận ngôn ngữ mà biểu thức chính quy (a|bc)^∗ biểu diễn. Tất nhiên ôtômat này phức tạp kinh khủng, và chắc chắn có ôtômat đơn giản hơn nhiều đoán nhận cùng ngôn ngữ đó. Để tìm nó, có thể dùng thuật toán chuyển NFA thành DFA rồi tối thiểu hoá ôtômat.

Tài liệu tham khảo

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools