Phép ghép hai ngôn ngữ chính quy

Cho hai ngôn ngữ chính quy L₁, L₂. Ta sẽ chứng minh phép ghép (nối) của chúng L = L₁ ∘ L₂ cũng là ngôn ngữ chính quy.

Phép ghép là gì

Ghép hai xâu “010” và “1111” ta được xâu “0101111”. Ghép hai ngôn ngữ, ta được một ngôn ngữ mới, xây dựng bằng cách ghép mỗi xâu của ngôn ngữ thứ nhất với mỗi xâu của ngôn ngữ thứ hai. Phép ghép hai xâu và hai ngôn ngữ được kí hiệu bằng dấu tròn nhỏ: ∘. Khi đó phép ghép hai ngôn ngữ L₁ và L₂ được định nghĩa như sau:

$$L_1\circ L_2=\{a\circ b|a\in L_1,b\in L_2\}$$

Ý tưởng chứng minh

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

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

Ta xây dựng ôtômat không đơn định A = ⟨Q, Σ, δ, q, F⟩ “chứa bên trong” cả hai ôtômat A₁ và A₂. Ý tưởng cơ bản là ta bắt đầu đoán nhận xâu bằng ôtômat A₁, và khi ôtômat A₁ đến một trạng thái kết thúc, ta thử đoán nhận phần còn lại của xâu bằng ôtômat A₂. Nếu ôtômat này cũng đoán nhận phần đó thì ôtômat A đoán nhận xâu.

Ví dụ

Cho ôtômat A₁ đoán nhận các xâu khác rỗng chỉ gồm chữ số 0 và các xâu gồm một chữ số 1 theo sau là toàn chữ số 0 (1, 10, 100, …):

và ôtômat A₂ đoán nhận các xâu kết thúc bằng 01:

Ta nối hai ôtômat bằng cách thêm các phép chuyển epsilon từ mọi trạng thái kết thúc của ôtômat A₁ đến trạng thái bắt đầu của ôtômat A₂, rồi biến các trạng thái kết thúc của A₁ thành trạng thái thông thường. Trạng thái bắt đầu của toàn bộ ôtômat mới là trạng thái bắt đầu của ôtômat A₁:

Ôtômat này hoạt động thế nào? Ta bắt đầu mô phỏng hoạt động của ôtômat A₁. Nếu chuyển sang trạng thái trước đây là trạng thái kết thúc q₁ hoặc q₂, ta biết rằng ôtômat A₁ đoán nhận một phần của xâu. Để toàn bộ xâu thuộc ngôn ngữ L₁ ∘ L₂, phần còn lại của xâu phải được ôtômat thứ hai A₂ đoán nhận – vì vậy từ mọi trạng thái trước đây là trạng thái kết thúc đều có phép chuyển epsilon đến trạng thái vốn là trạng thái bắt đầu của ôtômat A₂.

Ví dụ, xét xâu 0001. Xâu này thuộc phép ghép hai ngôn ngữ, vì nó có thể nhận được bằng cách ghép các xâu 00 ∘ 01. Nhưng nó cũng có thể nhận được bằng cách ghép các xâu 0 ∘ 001. Trong ôtômat của ta, có thể mô phỏng cả hai cách. Ôtômat có thể đi theo đường sau:

$$q_0{\to }^0{q}_1{\to }^0{q}_1{\to }^{\epsilon }{p}_0{\to }^0{p}_1{\to }^1{p}_2$$

Theo đường này, ôtômat trước hết “đoán nhận” phần xâu 00, sau đó là phần xâu 01. Hoặc ôtômat có thể đi theo đường sau:

$$q_0{\to }^0{q}_1{\to }^{\epsilon }{p}_0{\to }^0{p}_0{\to }^0{p}_1{\to }^1{p}_2$$

khi đó ôtômat trước hết “đoán nhận” phần xâu 0, rồi đến phần xâu 001. Tất nhiên, trong cả hai trường hợp ta đều đến trạng thái kết thúc p₂.

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

Nhắc lại: cho hai ngôn ngữ chính quy L₁, L₂ và hai ôtômat đoán nhận các ngôn ngữ đó:

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

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

• Q = Q₁ ∪ Q₂ (đồng thời giả sử Q₁ ∩ Q₂ = ∅)
• Σ= Σ₁ ∪ Σ₂
• q = q₀
• F = F₂

Hàm chuyển trạng thái δ được xây dựng theo từng trường hợp:

$$\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 \epsilon \\ {\delta }_1(q,a)\cup \left\{p_0\right\}& \text{nếu}& q\in F_1\wedge a=\epsilon \\ {\delta }_2(q,a)& \text{nếu}& q\in Q_2\end{array}$$

Tài liệu tham khảo

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