Persilangan bahasa nalar

Katakan kita mempunyai dua bahasa nalar L₁, L₂. Kita akan membuktikan bahawa persilangan kedua-duanya, L = L₁ ∩ L₂, juga merupakan bahasa nalar.

Idea bukti

Kita mempunyai dua bahasa nalar L₁ dan L₂ dan mahu membuktikan bahawa persilangannya, L₁ ∩ L₂, juga bahasa nalar. Oleh sebab L₁ dan L₂ ialah bahasa nalar, wujud automaton terhingga A₁ dan A₂ yang menerima bahasa L₁ dan L₂, iaitu L(A₁) = L₁ dan L(A₂) = L₂. Kita akan membina automaton terhingga A yang menerima bahasa L₁ ∩ L₂, dan dengan itu membuktikan bahawa bahasa L₁ ∩ L₂ ialah bahasa nalar.

Suatu rentetan tergolong dalam persilangan bahasa jika rentetan itu tergolong dalam bahasa L₁ dan juga dalam L₂. Maksudnya, rentetan itu mesti diterima oleh automaton A₁ dan juga oleh automaton A₂. Kita menggunakan idea yang sama sekali seperti dalam kesatuan bahasa nalar; hanya set keadaan akhir yang berubah.

Formalisasi kaedah

Kita mempunyai dua automaton,

$$\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 membina automaton A = ⟨Q, Σ, δ, q, F⟩ yang menerima bahasa L(A₁) ∩ L(A₂), dengan

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

Fungsi peralihan δ memenuhi 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

Katakan kita mempunyai automaton A₁ berikut, yang menerima semua rentetan yang mengandungi bilangan digit 1 yang genap:

dan automaton A₂, yang menerima rentetan yang mengandungi bilangan digit 0 yang ganjil:

Kita membina automaton yang menerima persilangan kedua-dua bahasa ini. Set keadaan automaton ini berbentuk Q = Q₁ × Q₂, keadaan awalnya ialah keadaan ⟨q₀, p₀⟩, dan keadaan akhirnya ialah F₁ × F₂:

Kemudian kita lengkapkan peralihan supaya δ(⟨q,p⟩, a) = ⟨δ₁(q, a), δ₂(p, a)⟩:

Contohnya, dalam automaton ini terdapat peralihan dari keadaan ⟨q₀, p₀⟩ bagi simbol 0 ke keadaan ⟨q₀,p₁⟩. Maksudnya, automaton A₁ mempunyai peralihan dari keadaan q₀ bagi simbol 0 kembali ke keadaan q₀, manakala automaton A₂ mempunyai peralihan bagi simbol 0 dari keadaan p₀ ke keadaan p₁.

Kita boleh mencuba automaton ini. Automaton ini sepatutnya menerima rentetan seperti 110 atau 00000 (rentetan ini mengandungi bilangan digit 1 yang genap dan juga bilangan digit 0 yang ganjil), tetapi tidak menerima rentetan seperti 11, 111, 1010.

Sumber

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