Bao đóng của ngôn ngữ chính quy

Cho ngôn ngữ chính quy L. Ta sẽ chứng minh bao đóng của ngôn ngữ L cũng là ngôn ngữ chính quy.

Bao đóng của ngôn ngữ là gì

Bao đóng (bao đóng Kleene) của ngôn ngữ L kí hiệu là L^∗. Bao đóng gồm mọi xâu có thể tạo được bằng cách ghép một số hữu hạn xâu của ngôn ngữ L. Có thể định nghĩa bao đóng như sau:

$$L^{\ast }=\{a_1\circ a_2\circ \cdots \circ a_n|a_i\in L,n\in \mathbb{N}\},$$

trong đó ∘ là phép ghép. Bao đóng chứa cả xâu rỗng, tức là ϵ.

Cách làm hình thức

Cách làm rất giống với trường hợp phép ghép hai ngôn ngữ. Chỉ khác là thay vì nối hai ôtômat khác nhau, ta nối một ôtômat với chính nó – từ các trạng thái kết thúc của ôtômat, ta vẽ các phép chuyển epsilon đến trạng thái bắt đầu của ôtômat. Tuy nhiên, bao đóng còn phải chứa xâu rỗng. Làm thế nào? Có thể biến trạng thái bắt đầu thành trạng thái kết thúc. Khi đó ôtômat sẽ đoán nhận xâu rỗng, nhưng cũng có thể đoán nhận thêm những xâu khác không thuộc bao đóng. Vì vậy, thay vào đó ta tạo một trạng thái bắt đầu mới và từ trạng thái này vẽ một phép chuyển epsilon đến trạng thái bắt đầu cũ.

Cho ngôn ngữ chính quy L₁ và ôtômat đoán nhận ngôn ngữ đó:

$$\begin{array}{rcl}{A}_1& =& ⟨Q_1,{\mathrm{\Sigma }}_1,{\delta }_1,q_0,F_1⟩\end{array}$$

Ta xây dựng ôtômat không đơn định A = ⟨Q, Σ, δ, q_s, F⟩ với:

• Q = Q₁ ∪ {q_s}
• Σ= Σ₁
• F = F₁ ∪ {q_s}

Hàm chuyển trạng thái δ được định nghĩa như sau:

$$\delta (q,a)=\{\begin{array}{lll}{\delta }_1(q,a)& \text{nếu}& q\in Q_1\wedge q\notin F_1\\ {\delta }_1(q,a)& \text{nếu}& q\in F_1\wedge a\ne ϵ\\ {\delta }_1(q,a)\cup \left\{q_0\right\}& \text{nếu}& q\in F_1\wedge a=ϵ\\ \left\{q_0\right\}& \text{nếu}& q=q_s\wedge a=ϵ\\ \mathrm{\varnothing }& \text{nếu}& q=q_s\wedge a\ne ϵ\end{array}$$

Ví dụ

Cho ôtômat A₁ đoán nhận các xâu 00 và 11:

Bao đóng của ngôn ngữ L(A₁) là ngôn ngữ gồm mọi xâu tạo bởi các cặp 00 và 11, chẳng hạn 0000, 110011, 11110000, … Để xây dựng ôtômat đoán nhận bao đóng này, ta tạo một trạng thái bắt đầu mới q_s có phép chuyển epsilon đến trạng thái bắt đầu cũ q₀, và thêm các phép chuyển epsilon từ các trạng thái q₃ và q₄ đến trạng thái q₀:

Có thể kiểm tra rằng ôtômat này đoán nhận các xâu 0000, 110011, 11110000, nhưng chẳng hạn không đoán nhận xâu 1010.

Tài liệu tham khảo

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