Konkatenasi bahasa reguler

Misalkan ada dua bahasa reguler L₁, L₂. Kita akan membuktikan bahwa konkatenasi (penyambungan) keduanya, L = L₁ ∘ L₂, juga merupakan bahasa reguler.

Apa itu konkatenasi

Konkatenasi dua string “010” dan “1111” menghasilkan string “0101111”. Konkatenasi bahasa menghasilkan bahasa baru yang dibentuk dengan menyambung setiap string dari satu bahasa dengan setiap string dari bahasa lainnya. Konkatenasi dua string maupun dua bahasa kita tulis dengan lingkaran kecil: ∘. Dengan begitu, konkatenasi bahasa L₁ dan L₂ dapat didefinisikan sebagai berikut:

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

Ide pembuktian

Ada dua bahasa reguler L₁, L₂ dan dua otomaton yang menerima bahasa-bahasa tersebut:

$$\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 nondeterministik A = ⟨Q, Σ, δ, q, F⟩ yang “memuat” kedua otomaton A₁ dan A₂. Ide dasarnya: kita mulai menerima string dengan otomaton A₁, dan ketika otomaton A₁ sampai di state akhir, kita mencoba menerima sisa string dengan otomaton A₂. Jika otomaton ini juga menerima bagian string tersebut, otomaton A menerima string tersebut.

Contoh

Misalkan ada otomaton A₁ berikut, yang menerima string tak kosong yang hanya tersusun atas angka nol, serta string yang terdiri atas angka satu yang diikuti hanya oleh angka nol (1, 10, 100, …):

Misalkan juga ada otomaton A₂ berikut, yang menerima string yang diakhiri 01:

Kedua otomaton kita sambung dengan menambahkan transisi epsilon dari semua state akhir otomaton A₁ ke state awal otomaton A₂, lalu state akhir A₁ kita jadikan state biasa. State awal otomaton baru secara keseluruhan adalah state awal otomaton A₁:

Bagaimana otomaton ini bekerja? Kita mulai menyimulasikan kerja otomaton A₁. Jika kita berpindah ke bekas state akhir q₁ atau q₂, kita tahu bahwa otomaton A₁ menerima sebagian string ini. Agar seluruh string termasuk bahasa L₁ ∘ L₂, sisa string masih harus diterima oleh otomaton kedua, A₂ — karena itulah dari semua bekas state akhir ada transisi epsilon ke state awal semula otomaton A₂.

Sebagai contoh, ambil string 0001. String ini termasuk konkatenasi kedua bahasa, karena dapat dibentuk dengan konkatenasi string 00 ∘ 01. Namun, string ini juga dapat dibentuk dengan konkatenasi string 0 ∘ 001. Pada otomaton kita, kedua cara dapat disimulasikan. Otomaton dapat menempuh jalur berikut:

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

Pada jalur ini, otomaton mula-mula “menerima” bagian string 00, lalu bagian string 01. Otomaton juga dapat menempuh jalur berikut:

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

sehingga otomaton mula-mula “menerima” bagian string 0, lalu bagian string 001. Pada kedua kasus, tentu saja kita sampai di state akhir p₂.

Prosedur formal

Sekali lagi: ada dua bahasa reguler L₁, L₂ dan dua otomaton yang menerima bahasa-bahasa tersebut:

$$\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 nondeterministik A = ⟨Q, Σ, δ, q, F⟩ dengan:

• Q = Q₁ ∪ Q₂ (sekaligus kita asumsikan Q₁ ∩ Q₂ = ∅)
• Σ= Σ₁ ∪ Σ₂
• q = q₀
• F = F₂

Fungsi transisi δ kita susun bagian demi bagian:

$$\delta (q,a)=\{\begin{array}{lll}{\delta }_1(q,a)& \text{jika}& q\in Q_1\wedge q\notin F_1\\ {\delta }_1(q,a)& \text{jika}& q\in F_1\wedge a\ne \epsilon \\ {\delta }_1(q,a)\cup \left\{p_0\right\}& \text{jika}& q\in F_1\wedge a=\epsilon \\ {\delta }_2(q,a)& \text{jika}& q\in Q_2\end{array}$$

Sumber

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