Irisan bahasa reguler

Misalkan ada dua bahasa reguler L₁, L₂. Kita akan membuktikan bahwa irisan keduanya, L = L₁ ∩ L₂, juga merupakan bahasa reguler.

Ide pembuktian

Ada dua bahasa reguler L₁ dan L₂, dan kita ingin membuktikan bahwa irisan keduanya, L₁ ∩ L₂, juga merupakan bahasa reguler. Karena L₁ dan L₂ adalah bahasa reguler, ada otomaton hingga A₁ dan A₂ yang menerima bahasa L₁ dan L₂, jadi berlaku L(A₁) = L₁ dan L(A₂) = L₂. Selanjutnya, kita susun otomaton hingga A yang menerima bahasa L₁ ∩ L₂. Dengan begitu, terbukti bahwa bahasa L₁ ∩ L₂ reguler.

Suatu string termasuk irisan bahasa jika string tersebut termasuk bahasa L₁ sekaligus L₂. Jadi, string tersebut harus diterima oleh otomaton A₁ sekaligus otomaton A₂. Kita gunakan ide yang persis sama seperti pada gabungan bahasa reguler, hanya himpunan state akhirnya yang kita ubah.

Formalisasi prosedur

Ada dua otomaton,

$$\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}$$

Kita konstruksi otomaton A = ⟨Q, Σ, δ, q, F⟩ yang menerima bahasa L(A₁) ∩ L(A₂), dengan

• Q = Q₁ × Q₂
• Σ= Σ₁ ∩ Σ₂
• q = ⟨q₀, p₀⟩
• F = F₁ × F₂

Untuk fungsi transisi δ berlaku hubungan berikut:

$$\mathrm{\forall }q\in Q_1,p\in Q_2:\delta (⟨q,p⟩,a)=⟨{\delta }_1(q,a),{\delta }_2(p,a)⟩$$

Contoh

Misalkan ada otomaton A₁ berikut, yang menerima semua string dengan banyak angka 1 genap:

dan otomaton A₂, yang menerima string dengan banyak angka 0 ganjil:

Kita konstruksi otomaton yang menerima irisan kedua bahasa ini. Himpunan state otomaton ini berbentuk Q = Q₁ × Q₂, state awalnya adalah state ⟨q₀, p₀⟩, dan state akhirnya adalah F₁ × F₂:

Selanjutnya, kita lengkapi transisinya sehingga δ(⟨q,p⟩, a) = ⟨δ₁(q, a), δ₂(p, a)⟩:

Pada otomaton ini, misalnya, dari state ⟨q₀, p₀⟩ ada transisi untuk simbol 0 ke state ⟨q₀,p₁⟩. Artinya, otomaton A₁ memiliki transisi untuk simbol 0 dari state q₀ kembali ke state q₀, sedangkan otomaton A₂ memiliki transisi untuk simbol 0 dari state p₀ ke state p₁.

Otomaton ini dapat kamu coba. Otomaton seharusnya menerima string seperti 110 atau 00000 (memuat angka 1 sebanyak genap sekaligus angka 0 sebanyak ganjil), tetapi tidak menerima string seperti 11, 111, 1010.

Sumber

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