KONSEP BAHASA DAN OTOMATA/AUTOMATA [ TEORI KOMPUTASI ]

1. Otomata

Otomata secara bahasa menurut American Heritage Dictionary adalah:

1. a robot; yang dapat diartikan sebagai mesin yang bergerak secara otomatis.

2. one that behaves in an automatic or mechanical fashion; sesuatu yang bersifat otomatis.

Istilah ini sudah dikenal sejak abad 17 yang terkait dengan misalnya : jam mekanik, mechanical-duck karya de Vaucanson (1738), mesin tenun otomatis (1745).

AUTOMATA

Dalam matematika istilah otomata terkait dengan teori mesin abstrak yang antara lain dapat didefinisikan secara sederhana sebagai : "Automata adalah mesin sekuensial otomatis yang menerima input dan mengeluarkan output yang keduanya dalam bentuk diskrit". Beberapa sistem yang dapat dibuat model otomatanya antara lain :

· Mesin Jaja / vending machine

· Kunci kombinasi

· Mesin penukar uang

· Model transmisi data

· Parser/compiler

Teori Otomata dan bahasa formal, berkaitan dalam hal :

¨ Pembangkitan kalimat/generator: menghasilkan semua kalimat dalam bahasa tertentu berdasarkan aturan yang dimilikinya.

¨ Pengenalan kalimat / recognition : menentukan suatu string (kalimat) termasuk sebagai salah satu anggota himpunan bahasa.

2. Bahasa Formal

Suatu kalimat dibentuk dengan menerapkan serangkaian aturan produksi pada sebuah simbol. Proses penerapan aturan produksi dapat digambarkan sebagai suatu diagram pohon.

Defenisi 1. sebuah string dengan panjang n yang dibentuk dari himpunan A adalah barisan dari n simbol

a₁a₂...a_n a_i Î A

Panjang string x dituliskan dengan |x|

Defenisi 2. String kosong (null string), dilambangkan dengan e adalah untaian dengan panjang 0 dan tidak berisi apapun. Panjang string e dituliskan dengan |e| = 0.

Defenisi 3. dua buah string a = a₁a₂...a_m dan b=b₁b₂...b_n dapat disambungkan menjadi string c dengan panjang m+n sebagai berikut c = a₁a₂...a_mb₁b₂...b_n

Operasi penyambungan tersebut dapat pula diterapkan pada himpunan

Z=XY = {st | s ÎX Ù tÎY}

Defenisi 4. (Closure). Aⁿ adalah himpunan string dengan panjang n yang dibentuk dari simbol-simbol di himpunan simbol/alfabet A:

Transitif Closure/Kleen Closure adalah himpunan seluruh string yang dapat dibentuk dari A dengan berbagai panjang

A^* = A⁰ È A¹ È A² È A³ È ...

Jika string kosong dikeluarkan , akan diperoleh positive closure

A⁺ = A¹ È A² È A³ È ...

3. Tata Bahasa

Aturan yang disebutkan pada proses pengenalan dan pembangkitan kalimat.

Secara formal, tata bahasa terdiri dari 4 komponen yaitu :

Himpunan berhingga, tidak kosong dari simbol-simbol terminal T

Himpunan berhingga, dari simbol-simbol non-terminal N

Simbol awal S Î N, yang merupakan salah satu anggota dari himpunan simbol non-terminal.

Himpunan berhingga aturan produksi P yang setiap elemennya dituliskan dalam bentuk :

a ® b

dimana a dan b adalah string yang dibentuk dari himpunan T È N dan a harus berisi paling sedikit satu simbol non-terminal.

Keempat komponen tersebut sering dituliskan sbb :

G = (T,N,S,P)

Bahasa yang dihasilkan oleh G ditulis sebagai L(G), yaitu himpunan string yang dapat diturunkan dari simbol awal S dengan menerapkan aturan-aturan produksi yang terdapat pada P.

Aturan Produksi

Aturan produksi a®b yang diterapkan pada suatu string w=aac mengganti kemunculan. a menjadi b, sehingga string tersebut berubah menjadi w=abc, sehingga dapat dituliskan aac Þ abc (aac memproduksi abc).

Produksi tersebut dapat diterapkan berkali-kali

w₁ Þ w₂ Þ w₃ Þ ... Þ w_n

atau dapat dituliskan

w₁Þ^* w_n

jika minimal harus ada 1 aturan produksi yang diterapkan :

w₁Þ⁺ w_n

Contoh 1.

Tata bahasa G = {{S} , {a,b}, N, P } dengan aturan produksi P adalah

S ® aSb

S ® e

maka dapat dihasilkan suatu string

S Þ aSb Þ aaSbb Þaabb

sehingga dapat dituliskan

S Þ^* aabb

Bahasa yang dihasilkan dari tatabahasa tersebut adalah

L(G) = { e , ab, aabb , aaabbb , aaaabbbb, ... }

atau dapat pula dituliskan

L(G) = {aⁿbⁿ | n ³ 0 }

Contoh 2.

Tata bahasa G = {{S,A} , {a,b}, S , P } dengan aturan produksi P adalah

S ® Ab

A ® aAb

A ® e

maka dapat dihasilkan suatu string

S Þ Ab Þb

S Þ Ab Þ aAbb Þ abb

S Þ Ab Þ aAbb Þ aaAbbb Þ aabbb

Bahasa yang dihasilkan dari tatabahasa tersebut adalah

L(G) = { b , abb, aabbb , aaabbbb , aaaabbbbb, ... }

atau dapat pula dituliskan

L(G) = {aⁿbⁿ⁺¹ | n ³ 0 }

4. Hirarki Chomsky

Tata bahasa (grammar) bisa didefenisikan secara formal sebagai kumpulan dari himpunan-himpunan variable, simbol-simbol terminal, simbol awal, yang dibatasi oleh aturan-aturan produksi. Pada tahun 1959 seorang ahli bahasa bernama Noam Chomsky menggolongkan bahasa ke dalam empat tingkatan yang disebut dengan hirarki Chomsky, seperti terlihat pada table 1.1 di bawah ini.

Tabel 1.1 Penggolongan Bahasa menurut Noam Chomsky

Kelas Bahasa	Mesin pengenal	Batasan Aturan Produksi
Regular language/ tipe 3	Finite State Automata	α adalah sebuah simbol variable/non-terminal β maksimal memiliki sebuah simbol variable/non-terminal yang bila ada terletak paling kiri/kanan.
Context free language/ tipe 2	Push Down Automata	α adalah sebuah simbol variabel
Context sensitive language/ tipe 1	Linear Bounded Automata	│α │≤ │β│
Unrestricted language/ tipe 0	Turing Machine	Tidak ada batasan

Tabel 1.2 Contoh sederhana masing-masing tingkatan bahasa

Kelas Bahasa	Ruas kiri	Ruas Kanan	Contoh
Regular	a Î N	£ 1 non terminal (paling kiri/kanan)	P ® abR Q ® abc R ® Scac
Context free	a Î N	-	P ® aQb Q ® abPRS
Context sensitive	a Î (TÈN)⁺	\|a\| £ \|b\|	aD ® Da AD ® aCD
Unrestricted	a Î (TÈN)⁺	-	CB ® DB ADc ® e

Ruas kiri harus memuat simbol non-terminal, contoh:

Q ® abc

R ® Scac

Pada contoh di atas, pada bahasa regular P ® abR, dapat dikatakan bahwa symbol non terminal P menghasilkan symbol “abR”. R adalah symbol non terminal yang dihasilkan dari symbol P, dimana R terletak paling kanan dari symbol yang dihasilkan. Q ® abc adalah symbol Q menghasilkan abc, dimana hasil tersebut semuanya dalam bentuk symbol yang terminal, yaitu semua sudah huruf kecil. R ® Scac adalah symbol non terminal R menghasilkan symbol Scac, dimana symbol non terminal S terletak paling kiri. Selain dari posisi symbol non terminal pada contoh di atas, apabila ada symbol non terminal yang terletak bukan paling kiri atau paling kanan, maka tatabahasa tersebut tidak termasuk ke dalam kelas bahasa regular.