ATURAN PRODUKSI SUATU FINITE STATE AUTOMATA 1

Aturan Produksi Bahasa Regular

Sebuah otomata berhingga menspesifikasikan sebuah bahasa sebagai himpunan semua untai yang menggerakkannya dari state awal ke salah satu dari state yang diterimanya (himpunan state akhir). Otomata berhingga pada gambar 1 menerima ekspresi regular:

a(a*∪b*)b

Selain dengan ekspresi regular, kita dapat mengkonstruksi aturan-aturan produksi untuk suatu tata bahasa regular. Kita ingat juga batasan aturan produksi untuk bahasa regular:

α → β

α adalah sebuah symbol variabel

β maksimal memiliki sebuah symbol variabel yang terletak di paling kanan bila ada. (bisa dibaca : α menghasilkan β), dimana α atau bisa berupa symbol terminal atau symbol non-terminal/variabel. Simbol variabel/non-terminal adalah symbol yang masih bisa diturunkan, sedang symbol terminal sudah tidak bisa diturunkan lagi. Simbol terminal biasanya dinyatakan dengan huruf kecil, missal a,b,c. Simbol non- terminal/variabel biasanya dinyatakan dengan huruf besar, missal A,B,C. Suatu tata bahasa (grammar) didefinisikan dengan 4 tupel (G={V,T,P,S}), dimana:

V = himpunan symbol variabel/non terminal
T = himpunan symbol terminal
P = kumpulan aturan produksi
S = symbol awal

Selanjutnya akan kita lihat bagaimana membuat kumpulan aturan produksi untuk suatu finite state automata.

Mengkonstruksi Aturan Produksi dari Suatu Finite State Automata

Dalam mengkonstruksi aturan produksi tata bahasa regular dari suatu finite state automata, perlu kita ingat yang menjadi perhatian kita adalah state-state yang bisa menuju ke state akhir. Mesin finite state automata di gambar 1 memiliki input ‘a’ dan ‘b’. Simbol ‘a’ dan ‘b’ akan menjadi symbol terminal pada aturan produksi yang akan kita bentuk. Misalnya kita tentukan symbol awal adalah S. Kita identikkan S dengan state awal q₀. Dari q₀ mendapat input a menjadi q₁. Bisa kita tuliskan sebagai aturan produksi:

S → aE

dimana E kita identikkan dengan q₁ (sebenarnya lebih tepatnya adalah bagian yang belum terbangkitkan mulai dari state q₁). Kita bisa menambahkan symbol variabel baru setiap kali kita perlukan. Dari q₁ mendapat transisi e (tanpa menerima input) ke q₂ dan q₃. Kita tuliskan:

E → A
E → B

bila kita identikkan q₂ sebagai A, dan q₃ sebagai B. Dari q₂ mendapat input a tetap ke q₂, dan dari q₃ mendapat input b tetap ke q₃, bisa kita tuliskan:

A → aA
B → bB

Selanjutnya kita lihat dari q₂ mendapat input b ke q₄, dan dari q₃ mendapat input b ke q₄, sementara q₄ state akhir dan dari q₄ tidak ada lagi busur keluar, maka bisa kita tuliskan:

A → b
B → b

Kumpulan aturan produksi yang kita peroleh bisa kita tuliskan sebagai berikut:

S → aE
E → A | B
A → aA | b
B → bB | b

Ingat ‘|’ berarti atau. Secara formal tata bahasa yang diperoleh dari otomata pada gambar 1:

V= { S,E,A,B}
T = {a,b}
P = { S → aE, E → A | B, A → aA | b, B → bB | b }
S = S

Kita lihat contoh lain pada gambar 2

Kita bisa mengkonstruksi aturan produksi untuk otomata tersebut:

T = {a,b}
S = S

Kumpulan aturan produksinya kita buat sebagai berikut:

S → aA | bB
(identikkan S untuk q₀, A untuk q₁, B untuk q₄)

A → bC
(identikkan C untuk q₂)

C → aS
(dari q₂ mendapat input a ke q₀)
( dari q₃ tidak ada transisi keluar dan bukan state akhir maka transisi ke q₃ kita abaikan)

B → bD
(identikkan D untk q₅)

D → bS
(dari q₅ mendapat input b ke q₀)
( dari q₆ tidak ada transisi keluar dan bukan state akhir maka transisi ke q₆ kita abaikan)

Pada kasus ini kita lihat q₀ sebagai state akhir masih memiliki transisi keluar, maka untuk menandakannya sebagai state akhir kita buat:
S → ε
*Bedakan dengan kasus gambar 1 dimana state akhir q₄ tidak memiliki transisi keluar.

Maka diperoleh:

V = { S,A,B,C,D}
P ={ S → aA|bB|ε, A → bC, B → bD, C → aS, D → bS }

Sebenarnya aturan produksi diatas masih dapat disederhanakan menjadi:
P ={ S → aA|bB|ε, A → baS, B → bbS }
Sehingga mereduksi jumlah symbol variabel yang diperlukan.