Ôtômat hữu hạn

Ôtômat hữu hạn (tiếng Anh: finite state machine hoặc finite automaton) là mô hình tính toán của một máy tính rất đơn giản. Ôtômat gồm một số trạng thái và một số phép chuyển trạng thái, và có thể đoán nhận hoặc từ chối xâu được đưa vào.

Ví dụ

Trước hết ta mô tả ôtômat hữu hạn một cách trực quan bằng đồ thị chuyển trạng thái:

Ôtômat gồm các trạng thái, trên hình là ba trạng thái hình tròn q₀, q₁ và q₂. Giữa các trạng thái có các phép chuyển, đó là các mũi tên. Ôtômat còn phải có trạng thái bắt đầu, ở đây là trạng thái q₀. Trạng thái bắt đầu thường được vẽ với một mũi tên đi vào nhưng không xuất phát từ trạng thái nào. Ngoài ra, ôtômat thường có trạng thái kết thúc, vẽ bằng nét đôi; trên hình đó là trạng thái q₂.

Ôtômat xây dựng như vậy đoán nhận một số xâu. Ta đưa xâu vào ôtômat, và ôtômat thử đoán nhận xâu đó. Nếu đoán nhận được, ôtômat trả lời CÓ; nếu không, ôtômat trả lời KHÔNG. Ôtômat của ta làm việc với các xâu tạo bởi các chữ “a, b, c”, nên có thể thử đoán nhận xâu “abbc”.

Ta xuất phát từ trạng thái bắt đầu q₀, đầu vào là xâu “abbc”. Tiếp theo ta đi theo các mũi tên.

Ta đọc xâu theo thứ tự thông thường từ trái sang phải, nghĩa là kí hiệu đầu tiên được xét là “a”. Mũi tên ứng với đầu vào “a” đi đến trạng thái q₁, nên ta chuyển sang đó và xoá kí hiệu “a” khỏi xâu. Đầu vào còn lại là xâu “bbc”:

Mũi tên ứng với đầu vào “b” quay về chính nút q₁. Ta lại xoá chữ đầu tiên, đầu vào còn lại là xâu “bc”, và ta vẫn ở trạng thái q₁. Cuối cùng đầu vào là xâu “c”. Từ trạng thái q₁, mũi tên ứng với đầu vào “c” đưa ta đến trạng thái q₂.

Ta đã đọc hết các chữ của xâu vào và đang ở trạng thái q₂, là trạng thái kết thúc. Vậy ôtômat hữu hạn này đoán nhận xâu “abbc”.

Nếu đọc xong mà không ở trạng thái chấp nhận, ôtômat sẽ không đoán nhận xâu. Ôtômat cũng không đoán nhận xâu nếu đến một trạng thái nào đó mà không có đường đi tiếp. Chẳng hạn, với đầu vào “ab” ta đến trạng thái q₁ và dừng ở đó – ôtômat không đoán nhận xâu này. Với xâu “aabbc” ta cũng không may, vì từ trạng thái q₁ không có mũi tên nào ứng với chữ “a”.

Như vậy, ôtômat hữu hạn dùng để nhận biết một tập hợp xâu nào đó. Trong thực tế, chẳng hạn có thể dùng ôtômat để kiểm tra xem xâu vào có phải là một địa chỉ email hợp lệ hay không.

Định nghĩa ôtômat hữu hạn

Hình dung trực quan ở trên về ôtômat hữu hạn cần được hình thức hoá để có thể làm việc với ôtômat tốt hơn.

Ta nói ôtômat hữu hạn (đơn định) là bộ năm ⟨Q, Σ, δ, q₀, F⟩, trong đó

• Q là tập hữu hạn các trạng thái,
• Σ (sigma hoa) là bảng chữ cái (tập hữu hạn các kí hiệu/chữ cái),
• δ: Q × Σ ⟶ Q là hàm chuyển trạng thái,
• q₀ ∈ Q là trạng thái bắt đầu,
• F ⊆ Q là tập các trạng thái kết thúc (trạng thái chấp nhận).

Quay lại ôtômat ở trên,

ta thấy tập trạng thái Q gồm ba trạng thái Q = {q₀, q₁, q₂}. Bảng chữ cái Σ gồm các chữ dùng để tạo nên các xâu mà ôtômat sẽ đoán nhận hoặc từ chối. Ở đây có lẽ đó là bảng chữ cái Σ= {a, b, c}, nhưng cũng có thể là một tập hợp bất kì chứa nó. Trạng thái bắt đầu q₀ là trạng thái q₀, không có gì thay đổi. Tập trạng thái kết thúc của ôtômat này chỉ có một trạng thái F = {q₂}.

Hàm chuyển trạng thái chính là ba mũi tên có ghi chữ. Nếu kí hiệu δ: Q × Σ ⟶ Q gây khó hiểu, thì kí hiệu này chỉ có nghĩa là δ là một hàm số (nói đúng hơn là ánh xạ) nhận hai tham số: một trạng thái thuộc Q và một chữ cái thuộc Σ. Khi gọi hàm, nó trả về một trạng thái mới. Hàm chuyển trạng thái của ta có thể cho bằng bảng như sau:

$$\begin{array}{ccc}Q& \mathrm{\Sigma }& \to Q\\ q_0& a& q_1\\ q_1& b& q_1\\ q_1& c& q_2\end{array}$$

Như vậy, khi gọi δ(q₁, c), ta áp dụng dòng thứ ba và hàm cho kết quả là trạng thái q₂ – đúng như trên đồ thị. Nếu ta đang ở trạng thái q₁ và đầu vào là chữ “c”, ta đi đến trạng thái q₂. Trước khi định nghĩa hình thức thế nào là ôtômat đoán nhận một xâu, ta dựa vào cách hiểu trực quan của khái niệm này và xét thêm một số ví dụ.

Thêm ví dụ

1. Xây dựng ôtômat trên bảng chữ cái nhị phân, tức là Σ= {0, 1}, chỉ đoán nhận các xâu kết thúc bằng chữ số 1. Chẳng hạn, ôtômat đoán nhận các xâu 1, 01, 000001, 0101011.

   

   Ôtômat có hai trạng thái – trạng thái bắt đầu q₀ và trạng thái kết thúc q₁. Mỗi khi đầu vào là chữ số 1, ta chuyển sang trạng thái kết thúc q₁ và ở lại đó. Ngược lại, nếu đầu vào là chữ số 0, ta chuyển sang trạng thái không kết thúc q₀ và cũng ở lại đó.

2. Xây dựng ôtômat trên bảng chữ cái nhị phân chỉ đoán nhận các xâu có chữ đầu tiên khác chữ cuối cùng.

   

   Ngay ở bước đầu tiên, ôtômat tách thành hai “ôtômat con”. Nếu xâu bắt đầu bằng 0, ôtômat đi vào phần bên trái và ở lại đó; nếu xâu bắt đầu bằng 1, ôtômat chuyển sang phần bên phải. Phần còn lại quen thuộc: nếu đang ở phần bên trái và đầu vào là 1, ta chuyển sang trạng thái kết thúc và ở lại đó. Nếu đầu vào là 0, ta chuyển sang trạng thái q₁, không phải trạng thái kết thúc.

   Khác với các ôtômat trước, ôtômat này có nhiều trạng thái kết thúc, cụ thể F = {q₃, q₄}.

3. Xây dựng ôtômat trên bảng chữ cái nhị phân chỉ đoán nhận các xâu không chứa hai chữ số 0 liền nhau.

   

   Ôtômat này thú vị vì hai lí do. Thứ nhất, nó đoán nhận xâu rỗng. Ta có thể thử đưa xâu rỗng vào ôtômat, và ôtômat sẽ đoán nhận xâu đó nếu trạng thái bắt đầu đồng thời là trạng thái kết thúc, như ở ôtômat này. Vì xâu rỗng là xâu không chứa hai chữ số 0 liền nhau, nên kết quả này là đúng. Thứ hai, mọi trạng thái của ôtômat này đều là trạng thái kết thúc. Trường hợp duy nhất ôtômat không đoán nhận xâu là khi từ trạng thái hiện tại không có phép chuyển nào. Điều đó xảy ra ở trạng thái q₁: trạng thái này không có phép chuyển ứng với 0, vì khi đó xâu sẽ chứa hai chữ số 0 liền nhau.

4. Xây dựng ôtômat trên bảng chữ cái {-,+,.,0,1,…,9} chỉ đoán nhận các xâu biểu diễn một số. Đó có thể là số nguyên, chẳng hạn 2, 548, 98263, hoặc số thập phân viết với dấu chấm như trong lập trình, chẳng hạn 5584.48, 3.14; cả hai loại đều có thể có dạng số âm với dấu trừ -2, -548, -3.14 và có thể có dấu cộng viết rõ, tức là +2, +548, +3.14. Đồng thời, số 0.123 cũng có thể viết là .123 (không có chữ số 0 ở đầu), kể cả khi có dấu cộng hoặc dấu trừ. Ta dùng kí hiệu phụ N thay cho việc vẽ 10 phép chuyển ứng với 10 chữ số.

   

5. Xây dựng ôtômat trên bảng chữ cái nhị phân chỉ đoán nhận các xâu có dạng 0ⁿ1ⁿ, nghĩa là xâu bắt đầu bằng một số chữ số 0, tiếp theo là cùng số lượng chữ số 1. Ví dụ các xâu như vậy là 0011, 00001111, 01.

   Không thể xây dựng ôtômat như vậy, vì ôtômat không có chỗ nào để “nhớ” số chữ số 0. Ta sẽ phải tạo nhiều “ôtômat con”, giống như ở ví dụ thứ hai, nhưng số “ôtômat con” sẽ phải là vô hạn, mỗi giá trị n một ôtômat.

Hình thức hoá quá trình tính toán của ôtômat

Ta đã định nghĩa hình thức bản thân ôtômat hữu hạn. Tiếp theo cần định nghĩa ôtômat thực sự làm gì, tức là định nghĩa quá trình tính toán của ôtômat.

Cấu hình của ôtômat: Ta nói cặp ⟨q, w⟩ ∈ Q × Σ^∗ là một cấu hình của ôtômat, trong đó q là trạng thái hiện tại của ôtômat và w là phần xâu chưa đọc. Σ^∗ là bao đóng của bảng chữ cái Σ, tức là tập hợp tất cả các xâu tạo được từ các chữ cái của Σ. Bao đóng này chứa cả xâu rỗng, kí hiệu là ε.

Cho ôtômat ⟨Q, Σ, δ, q₀, F⟩. Khi ôtômat bắt đầu đoán nhận xâu w, nó ở cấu hình ban đầu ⟨q₀, w⟩. Quay lại ôtômat ở trên:

Nếu muốn đoán nhận xâu w = abbc, cấu hình ban đầu là ⟨q₀, abbc⟩.

Bước tính toán được định nghĩa là quan hệ ↦ giữa các tập hợp (Q × Σ^∗) × (Q × Σ^∗), tức là giữa các cấu hình của ôtômat. Giả sử w = w₀w₁… w_n là phần chưa đọc của xâu w. Ta nói hai cấu hình ⟨q₁, w₀w₁… w_n⟩ và ⟨q₂, w₁… w_n⟩ có quan hệ ↦, viết là

$$⟨q_1,w_0{w}_1\dots w_n⟩\mapsto ⟨q_2,w_1\dots w_n⟩,$$

khi và chỉ khi δ(q₁, w₀) = q₂. Quay lại ví dụ, cấu hình ban đầu là ⟨q₀, abbc⟩. Trên đồ thị ta thấy với đầu vào “a” ta có thể chuyển sang trạng thái q₁. Vậy có thể viết

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩,$$

vì δ(q₀, a) = q₁. Như vậy ta đã thực hiện một bước tính toán: xem với đầu vào hiện tại (= chữ đầu tiên của phần xâu chưa đọc) cần đi đến trạng thái nào, chuyển sang trạng thái đó và xoá chữ đầu tiên khỏi phần xâu chưa đọc. Kết quả là một cấu hình mới.

Bao đóng phản xạ và bắc cầu của quan hệ bước tính toán kí hiệu là ↦ ^∗. Viết K₁ ↦ ^∗ K₂, trong đó K₁, K₂ là các cấu hình của ôtômat, có nghĩa là từ cấu hình K₁ ta có thể đi đến cấu hình K₂ qua một số bước tính toán, hay nói cách khác, tồn tại một dãy hữu hạn các cấu hình sao cho:

$$K_1\mapsto K_{11}\mapsto K_{12}\mapsto K_{13}\mapsto \cdots \mapsto K_2$$

Chẳng hạn, ở ôtômat của ta có ⟨q₀, abbc⟩ ↦ ^∗ ⟨q₁,bc⟩, vì sau hai bước tính toán còn lại xâu “bc” và ta ở trạng thái q₁. Tức là tồn tại dãy cấu hình sau:

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩\mapsto ⟨q_1,bc⟩$$

Ôtômat đoán nhận xâu w khi và chỉ khi tồn tại q_f ∈ F sao cho $$⟨q_0,w⟩{\mapsto }^{\ast }⟨q_f,\epsilon ⟩$$ Nghĩa là ôtômat đoán nhận xâu w khi và chỉ khi tồn tại một dãy bước tính toán mà ở cuối dãy, ta đã đọc hết xâu và đang ở một trạng thái kết thúc của ôtômat. Xâu đã được đọc hết thể hiện ở chỗ: trong cấu hình, ở vị trí của xâu là ε, tức là xâu rỗng. Ôtômat của ta đoán nhận xâu abbc, vì tồn tại dãy cấu hình sau:

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩\mapsto ⟨q_1,bc⟩\mapsto ⟨q_1,c⟩\mapsto ⟨q_2,\epsilon ⟩$$

và q₂ là trạng thái kết thúc, q₂ ∈ F.

Ngôn ngữ do ôtômat đoán nhận là tập hợp tất cả các xâu mà ôtômat đoán nhận. Ngôn ngữ của ôtômat A kí hiệu là L(A). Như vậy L(A) ⊆ Σ^∗ và

$$L(A)=\{w\in {\mathrm{\Sigma }}^{\ast }|A\text{ đoán nhận xâu }w\}$$

Ngôn ngữ chính quy là ngôn ngữ do một ôtômat hữu hạn nào đó đoán nhận.

Hai ôtômat hữu hạn gọi là tương đương nếu chúng đoán nhận cùng một ngôn ngữ. Tức là hai ôtômat A₁ và A₂ tương đương nếu L(A₁) = L(A₂).

Tài liệu tham khảo

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