Hợp của hai ngôn ngữ chính quy

Cho hai ngôn ngữ chính quy L₁, L₂. Ta sẽ chứng minh hợp của chúng L = L₁ ∪ L₂ cũng là ngôn ngữ chính quy.

Cách làm bằng ôtômat đơn định

Ý tưởng

Cho hai ngôn ngữ chính quy L₁ và L₂, ta muốn chứng minh hợp L₁ ∪ L₂ của chúng cũng là ngôn ngữ chính quy. Vì L₁ và L₂ là ngôn ngữ chính quy nên tồn tại các ôtômat hữu hạn A₁ và A₂ đoán nhận các ngôn ngữ L₁ và L₂, tức là L(A₁) = L₁ và L(A₂) = L₂. Ta sẽ xây dựng ôtômat hữu hạn A đoán nhận ngôn ngữ L₁ ∪ L₂, qua đó chứng minh ngôn ngữ L₁ ∪ L₂ là chính quy.

Làm thế nào? Ta có sẵn các ôtômat hữu hạn A₁ và A₂ đoán nhận từng ngôn ngữ. Có thể nói xâu w thuộc ngôn ngữ L₁ ∪ L₂ khi và chỉ khi ít nhất một trong hai ôtômat A₁, A₂ đoán nhận xâu đó.

Ôtômat A có thể hoạt động như sau: với đầu vào w, nó mô phỏng quá trình tính toán của ôtômat A₁ trên đầu vào w. Nếu A₁ đoán nhận xâu w thì A cũng đoán nhận xâu w. Nếu A₁ từ chối xâu w, thì A thử mô phỏng tiếp quá trình tính toán của A₂ trên đầu vào w. Nếu A₂ đoán nhận xâu w thì A cũng đoán nhận xâu w. Trái lại, ôtômat này từ chối.

Chỉ còn phải hình thức hoá: ôtômat A “mô phỏng” quá trình tính toán của một ôtômat khác nghĩa là gì.

Hình thức hoá

Cho hai ngôn ngữ chính quy L₁ và L₂ lần lượt do các ôtômat hữu hạn sau đoán nhận

$\begin{array}{rcl} A_{1} & = & ⟨ Q_{1}, Σ_{1}, δ_{1}, q_{1}, F_{1} ⟩ \\ A_{2} & = & ⟨ Q_{2}, Σ_{2}, δ_{2}, q_{2}, F_{2} ⟩ . \end{array}$

Ta xây dựng ôtômat hữu hạn A = ⟨Q, Σ, δ, q, F⟩ đoán nhận ngôn ngữ L = L₁ ∪ L₂, dựa trên ý tưởng mô phỏng hai ôtômat A₁, A₂. Giả sử đầu vào là xâu w = w₁w₂… w_n và ta mô phỏng đồng thời hoạt động của các ôtômat A₁ và A₂ trên xâu w. Cấu hình ban đầu của ôtômat A₁ là ⟨q₁, w₁w₂… w_n⟩, cấu hình ban đầu của A₂ là ⟨q₂, w₁w₂… w_n⟩. Thực hiện một bước tính toán ở mỗi ôtômat, ta được các cấu hình ⟨δ₁(q₁, w₁), w₂… w_n⟩ và ⟨δ₂(q₂, w₁), w₂… w_n⟩.

Ta thấy hai cấu hình này chỉ khác nhau ở thành phần thứ nhất, còn thành phần thứ hai – phần xâu chưa đọc – luôn giống nhau. Vì vậy, khi mô phỏng, ta không cần lưu hai cấu hình của hai ôtômat mà chỉ cần một cấu hình dạng ⟨⟨q_i, q_j⟩, w_l… w_n⟩, trong đó q_i ∈ Q₁ và q_j ∈ Q₂. Nói cách khác, ôtômat A đang xây dựng có cấu hình ban đầu ⟨⟨q₁, q₂⟩, w⟩. Thành phần thứ nhất của cặp ⟨q₁, q₂⟩ là trạng thái hiện tại của ôtômat A₁, thành phần thứ hai là trạng thái hiện tại của ôtômat A₂.

Như vậy, có thể nói tập trạng thái của ôtômat A đang xây dựng là Q = Q₁ × Q₂, tức là tích Descartes của các tập trạng thái của hai ôtômat ban đầu. Ý tưởng tiếp theo là ôtômat A có trạng thái bắt đầu ⟨q₁, q₂⟩, và nếu khi đọc kí hiệu w₁, ôtômat A₁ chuyển sang trạng thái q_i, còn ôtômat A₂ với cùng kí hiệu w₁ chuyển sang trạng thái q_j, thì với kí hiệu w₁ ôtômat A chuyển sang trạng thái ⟨q_i, q_j⟩.

Hàm chuyển trạng thái δ được viết như sau (ở đây giả sử hai ôtômat đang ở các trạng thái q_i và q_j):

$δ (⟨ q_{i}, q_{j} ⟩, w) = ⟨ δ_{1} (q_{i}, w), δ_{2} (q_{j}, w) ⟩$

Chỉ còn vài chi tiết nhỏ. Bảng chữ cái là Σ= Σ₁ ∪ Σ₂. Trạng thái bắt đầu là q = ⟨q₁, q₂⟩. Các trạng thái kết thúc là mọi cặp ⟨q_i, q_j⟩ sao cho q_i ∈ F₁ hoặc q_j ∈ F₂.

Minh hoạ

Cho hai ôtômat. Ôtômat thứ nhất A₁ đoán nhận mọi xâu (kể cả xâu rỗng) mà trong đó các chữ số 0 và 1 xen kẽ nhau, tức là các xâu dạng 01, 0101, 010101, …

Ôtômat thứ hai A₂ đoán nhận các xâu chứa ít nhất một chữ số 0:

Hợp của hai ngôn ngữ này gồm các xâu hoặc chứa chữ số 0, hoặc có dạng 01, 0101, … Bây giờ ta xây dựng ôtômat hữu hạn A = ⟨Q, Σ, δ, q, F⟩ đoán nhận đúng ngôn ngữ hợp này. Trước hết, ta xem các trạng thái của ôtômat mới A. Đó là tích Descartes của tập trạng thái của ôtômat thứ nhất và ôtômat thứ hai:

$Q = Q_{1} \times Q_{2} = {⟨ q_{0}, p_{0} ⟩, ⟨ q_{0}, p_{1} ⟩, ⟨ q_{1}, p_{0} ⟩, ⟨ q_{1}, p_{1} ⟩, ⟨ q_{2}, p_{0} ⟩, ⟨ q_{2}, p_{1} ⟩}$

Đó là sáu trạng thái của ôtômat A đoán nhận ngôn ngữ hợp L(A₁) ∪ L(A₂). Trên đồ thị chuyển trạng thái, chúng như sau:

Đừng lo khi thấy các trạng thái được tạo từ cặp trạng thái – điều đó chỉ giúp dễ theo dõi những gì diễn ra trong ôtômat. Các trạng thái hoàn toàn có thể đặt tên thông thường là q₀, …, q₅. Các trạng thái kết thúc là những trạng thái chứa q₀ hoặc p₁, là các trạng thái kết thúc của hai ôtômat ban đầu. Trạng thái bắt đầu là ⟨q₀, p₀⟩.

Bây giờ cần tìm mọi phép chuyển. Ta lập bảng sau:

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ \end{array}$

Ta lần lượt điền vào bảng. Trước hết, ta xác định phép chuyển từ trạng thái ⟨q₀, p₀⟩ với đầu vào 0 đi đến đâu. Ở ôtômat A₁, phép chuyển từ trạng thái q₀ với đầu vào 0 đi đến trạng thái q₁. Ở ôtômat A₂, phép chuyển từ p₀ với chữ số 0 đi đến trạng thái p₁. Vì vậy, ta ghi vào bảng ⟨q₁, p₁⟩:

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ & ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ \end{array}$

Với đầu vào 1: ở ôtômat A₁ ta có δ₁(q₀, 1) = q₂, ở ôtômat A₂ ta có δ₂(p₀, 1) = p₀. Như vậy ta được trạng thái ⟨q₂, p₀⟩.

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ & ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ \end{array}$

Điền nốt phần còn lại của bảng:

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ & ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ & ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{0}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ \end{array}$

Dựa vào bảng này, ta chỉ cần vẽ nốt phần còn lại của đồ thị.

Ta có thể kiểm tra ôtômat hoạt động đúng. Thử đoán nhận xâu 0100. Ôtômat lần lượt đi qua các trạng thái

$⟨ q_{0}, p_{0} ⟩, ⟨ q_{1}, p_{1} ⟩, ⟨ q_{0}, p_{1} ⟩, ⟨ q_{1}, p_{1} ⟩, ⟨ q_{2}, p_{1} ⟩$

Vì ⟨q₂, p₁⟩ là trạng thái kết thúc nên ôtômat A đoán nhận xâu 0100. Điều gì xảy ra nếu ta thử đoán nhận xâu 0100 bằng các ôtômat A₁ và A₂? Ôtômat A₁ lần lượt đi qua các trạng thái sau:

$q_{0}, q_{1}, q_{0}, q_{1}, q_{2}$

Ôtômat dừng ở trạng thái q₂, không phải trạng thái kết thúc, nên ôtômat A₁ không đoán nhận xâu này. Còn ôtômat A₂?

$p_{0}, p_{1}, p_{1}, p_{1}, p_{1}$

Trạng thái p₁ là trạng thái kết thúc, nên ôtômat A₂ đoán nhận xâu 0100. Lưu ý rằng các ôtômat A₁ và A₂ dừng ở các trạng thái q₂ và p₁, phù hợp với việc ôtômat A dừng ở trạng thái ⟨q₂, p₁⟩.

Cách làm bằng ôtômat không đơn định

Ví dụ

Tính đóng của lớp ngôn ngữ chính quy đối với phép hợp cũng có thể chứng minh bằng cách xây dựng một ôtômat không đơn định; cách này đơn giản hơn nhiều.

Cho hai ngôn ngữ chính quy L₁, L₂, ta muốn chứng minh hợp của chúng L = L₁ ∪ L₂ cũng là ngôn ngữ chính quy. Vì L₁, L₂ là ngôn ngữ chính quy nên phải tồn tại các ôtômat A₁, A₂ đoán nhận các ngôn ngữ đó, tức là L(A₁) = L₁ và L(A₂) = L₂. Từ các ôtômat này, ta xây dựng ôtômat A đoán nhận ngôn ngữ L, tức là L(A) = L.

Giả sử các ôtômat hữu hạn A₁ và A₂ như sau:

và

Để xây dựng ôtômat đoán nhận hợp của hai ngôn ngữ, ta tạo một trạng thái bắt đầu mới và từ trạng thái này vẽ hai phép chuyển epsilon đến các trạng thái bắt đầu của hai ôtômat ban đầu. Chỉ có vậy. Ôtômat như sau:

Hình thức hoá

Cho hai ôtômat A₁ = ⟨Q₁, Σ, δ₁, q₁, F₁⟩ và A₂ = ⟨Q₂, Σ, δ₂, q₂, F₂⟩. Ta xây dựng ôtômat A = ⟨Q, Σ, δ, q₀, F⟩ đoán nhận hợp của các ngôn ngữ do hai ôtômat trên đoán nhận, tức là L(A) = L(A₁) ∪ L(A₂). Trong đó:

Q = Q₁ ∪ Q₂ ∪ {q₀}
F = F₁ ∪ F₂

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

$δ (q, a) = {\begin{cases} δ_{1} (q, a) & nếu & q \in Q_{1} \\ δ_{2} (q, a) & nếu & q \in Q_{2} \\ {q_{1}, q_{2}} & nếu & q = q_{0} \land a = ε \\ \emptyset & nếu & q = q_{0} \land a \neq ε \end{cases}$

Tài liệu tham khảo

Mục lục: Tính đóng của ngôn ngữ chính quy, Hợp của hai ngôn ngữ chính quy, Giao của hai ngôn ngữ chính quy, Hiệu của hai ngôn ngữ chính quy, Phần bù của ngôn ngữ chính quy, Phép ghép hai ngôn ngữ chính quy, Bao đóng của ngôn ngữ chính quy

« Bài trước: Tính đóng của ngôn ngữ chính quy

Bài tiếp: Giao của hai ngôn ngữ chính quy »