BAB 2

PEMBAHASAN

1.1. Teori-Teori Otomata

1.1.1.Sejarah Otomata

Otomata bermula sebelum komputer ada pada teori di bidang sistem logika

matematika atau formal, ilmuwan David Hilbert telah mencoba menciptakan

algoritma umum untuk pembuktian (seluruh) persoalan matematika secara

otomatis yaitu mampu menentukan salah benarnya sembarang prosisi

matematika.

Tahun 1931, KurtGdel mempublikasikan teori ketidaklengkapan dimana

membuktikan prosedur/algoritma yang dikehendaki David Hilbert tersebut

tidak akan pernah ada. KurtGdel membangun rumus di kalkulus predikat yang

diterapkan pada bilangan bulat yang memiliki pernyataan-pernyataan definisi

yang tidak dapat dibuktikan maupun dibantah di dalam sistem logika yang

mungkin dibangun manusia.

Formalisasi argumen teorema ketidaklengkapan KurtGdel ini berikut

penjelasan dan formalisasi selanjutnya dari prosedur efektif secara intuisi

merupakan salah satu pencapaian intelektual terbesar abad 20, yaitu abad

dimana formalisasi berkembang semarak.

Sekitar tahun 1950-an, Noam Chomsky menciptakan model matematika

sebagai sarana untuk mendeskripsikan bahasa serta menjawab pertanyaan-

pertanyaan di atas. Saat ini dimulai pendalaman bidang bahasa computer.

Sekitar tahun 1950-an, Noam Chomsky menciptakan model matematika

sebagai sarana untuk mendeskripsikan bahasa serta menjawab pertanyaan-

pertanyaan di atas. Saat ini dimulai pendalaman bidang bahasa komputer.

Perbedaan antara bahasa komputer dan bahasa manusia adalah sampai

sekarang belum diketahuinya bagaimana cara manusia mengartikan bahasa,

sementara dengan pasti dapat mengartikan bahasa pada komputer. Noam

Chomsky mengemukakan perangkat format disebut grammar untuk

2

memodelkan properti-properti bahasa. Tata bahasa (grammer) bisa

didefinisikan secara, formal sebagai kumpulan dari himpunan? himpunan

variabel, simbol?simbol, terminal, simbol awal, yang dibatasi oleh aturan-

aturan produksi. Tingkat bahasa dapat digolongkan menjadi empat yaitu :

1.Bahasa : Regular type 3

Mesin otomata : Finite State Otomata (FSA) meliputi deterministic finite

automata dan non deterministic finite automata

Batasan aturan produksi : adalah sebuah simbol variabel maksimal

memiliki sebuah simbol variabel yang bila terletak di posisi paling kanan.

2.Bahasa : Bebas konteks/context free /type 2

Mesin otomata : Push down automata (PDA)

Batasan aturan produksi : Berupa sebuah simbol variabel.

3.Bahasa : Context sensitive/type 1

Mesin otomata : Linier bounded automata

Batasan aturan produksi :

4.Bahasa : Unrestricted /phase /natural language/type 0

Mesin otomata : Mesin turing

Batasan aturan produksi : Tidak ada batasan

2.1.1 Definisi Otomata

Teori Bahasa

Teori bahasa membicarakan bahasa formal (formal language),

terutama untuk kepentingan perancangan kompilator (compiler) dan

pemroses naskah (text processor).

Bahasa formal adalah kumpulan kalimat. Semua kalimat dalam

sebuah bahasa dibangkitkan oleh sebuah tata bahasa (grammar) yang

sama.

Sebuah bahasa formal bisa dibangkitkan oleh dua atau lebih tata

bahasa berbeda.

Dikatakan bahasa formal karena grammar diciptakan mendahului

pembangkitan setiap kalimatnya.

3

Bahasa Natural/manusia bersifat sebaliknya; grammar diciptakan

untuk meresmikan kata-kata yang hidup di masyarakat. Dalam

pembicaraan selanjutnya ‘bahasa formal’ akan disebut ‘bahasa’ saja.

Otomata (Automata)

Otomata adalah mesin abstrak yang dapat mengenali (recognize),

menerima (accept), atau membangkitkan (generate) sebuah kalimat dalam

bahasa tertentu.

1.2. Mesin Tuning

1.2.1. Keterbatasan FSA dan PDA

Tidak semua jenis bahasa dapat dikenali oleh FSA atau PDA.

Sebagaimana telah diuraikan di pembahasan sebelumnya bahwa

kelemahan FSA adalah bahwa ia tidak mampu ‘mengingat’ simbol-

simbol yang pernah dibaca. Kelemahan FSA inilah yang kemudian

diatasi oleh PDA. Tetapi ternyata PDA juga memiliki kelemahan, yaitu

meskipun PDA dapat mengingat simbol yang dibaca dengan stack, tetapi

simbol stack hanya dapat diases dari satu arah, yaitu hanya simbol-

simbol teratas.

Mesin Turing dirancang mengatasi kelemahan FSA dan PDA, yaitu

dengan merepresentasikan logika kerja mesin tidak menggunakan stack

sebagaimana representasi dalam PDA, tetapi menggunakan representasi

pita yang dapat dibaca dan ditulisi. Mesin turing diwakili oleh sebuah

pita panjang takterhingga. Pada pita dapat ditulis/ dibacakan sebuah

simbol. Setelah pita ditulisi maka simbol pada pita kemudian akan

berubah menjadi simbol yang baru saja dituliskan.

1.2.2. Definisi Mesin Tuning

Mesin Turing adalah model komputasi teoritis yang ditemukan oleh

Alan Turing, berfungsi sebagai model ideal untuk melakukan

perhitungan matematis. Walaupun model ideal ini diperkenalkan sebelum

4

komputer nyata dibangun, model ini tetap diterima kalangan ilmu

komputer sebagai model komputer yang sesuai untuk menentukan

apakah suatu fungsi dapat selesaikan oleh komputer atau tidak

(menentukan computable function). Mesin Turing terkenal dengan

ungkapan "Apapun yang bisa dilakukan oleh Mesin Turing pasti bisa

dilakukan oleh komputer."

Mesin Turing merupakan mesin yang merepresentasikan tata bahasa

unrestricted. Mesin Turing ini bersifat umum dan memiliki kemampuan

yang lebih tinggi dari finite state automata maupun push down automata

dari segi aksi dan komponennya. Pada mesin Turing memori akan berupa

suatu pita yang pada dasarnya berupa array (deretan) sel-sel

penyimpanan. Setiap sel mampu menyimpan sebuah simbol tunggal.

Mesin Turing bisa dianalogikan seperti komputer sederhana. Dengan

sejumlah state sebagai memori, pita sebagai secondary storage, dan

fungsi transisi sebagai program.

Sebuah mesin Turing secara formal dinyatakan dalam 7 tupel

M={ Q, Σ, Г, S, F, b, δ }, dimana :

Q = himpunan state

Σ = kumpulan simbol input

Г = simbol dalam pita (meliputi juga blank)

S = state awal, S Q

F = himpunan state akhir

b = simbol kosong (blank), bukan bagian dari Σ

δ = fungsi transisi : Q X Г Q X Г X {R,L}

R = posisi baca/tulis bergerak kekanan (RIGHT)

L = posisi baca/tulis bergerak kekiri (LEFT)

Bagian pada pita yang belum ditulisi dianggap berisi simbol b.

Sebuah mesin turing terdiri atas barisan sel tersusun berupa pita yang

dapat bergerak maju mundur, komponen aktif baca/tulis pita yang

memiliki status perhitungan serta dapat mengubah/menulisi sel aktif yang

5

ada di pita tadi, dan suatu kumpulan instruksi bagaimana komponen

baca/tulis ini harus melakukan modifikasi terhadap sel aktif pada pita,

serta bagaimana menggerakkan pita tersebut. Pada setiap langkah dalam

komputasi, mesin ini akan dapat mengubah isi dari sel yang aktif,

mengubah status dari komponen baca/tulis, dan mengubah posisi pita ke

kiri atau kekanan.

Sebagai input dari mesin turing adalah kata atau untai atas suatu

alfabet T. Mesin turing berhenti dengan keadaan menerima atau menolak

untai. Kadang-kadang terjadi pula perulangan atau looping tak terhingga.

Keterangan :

Tape : Tempat diletakannya inputan yang berupa kata/untai.

Head : membaca dan menulisi sel pita mesin turing, bisa bergerak

ke kiri atau ke kanan.

Finite State Control (FSC) : otak dari TM, diimplementasikan dari

algoritma pengenalan kalimat.

6

Palindrome itu adalah berasal dari bahasa Yunani yaitu Palindromos

A Palindrome. Palindromos A Palindrome adalah kata atau kalimat yang

sama dieja maju atau mundur (bacaan yang sama dieja pada kedua arah).

Sebagai contoh sederhana adalah beberapa kata yang sederhana yaitu

rotor, rotator, civic, madam, racecar, level, dan lain-lain. Untuk contoh

lain yaitu kalimat palindrome adalah No lemon no melon, No devil lived

on, Swap God for a janitor rot in a jar of dog paws, dan lain-lain.

Dibawah ini adalah graf dari palindrome detector , merupakan

sebuah simulasi mesin turing yang berfungsi untuk mendeteksi kata

palindrome yang diinputkan oleh user. Kata atau untai yang dibentuk

masih terbatas pada penggunaan huruf “A” dan “B”. Contoh kata yang

dibentuk adalah “ABAABBA” untuk kata yang tidak termasuk dalam

palindrome, dan “BABBAB” untuk kata yang termasuk dalam

palindrome.

7

Pemrograman sederhana jenis mesin Turing ini tidak sesulit yang

dibayangkan. Dimana sebenarnya pemrograman ini akan membentuk

graph. Transisi state terdiri dari 5-tupel rangkaian pada setiap baris,

dengan format seperti ini:

[state],[karakter],[state baru],[karakterbaru],[arah]

1 , _ , 2 , # , >

2 , A , 3 , A , >

Karakter '_' dapat digunakan untuk menunjukkan kosong (blank),

'H' untuk menunjukkan sebagai state berhenti/Halt (hanya berlaku pada

sisi kanan transisi), dan '<' dan '>' untuk menunjukkan arah masing-

masing bergerak ke kiri atau kanan.

1.2.3. Gerakan Mesin Turing

Gerakan mesin turing diwakili oleh fungsi transisi :

δ (qi,a)=(qj,b,X) : Mesin kedudukan qi membaca simbol masukan a,

gerakan : mesin berubah ke status qj, menulis b dan posisi baca /tulis

bergerak X (berupa R=gerak ke kanan atau L=gerak ke kiri).

Contoh gerakan mesin

Untuk gerakan fungsi transisi δ (q1,a)=(q3,b,R) artinya:

8

Gambar 2.1 Posisi mesin awal sebelum membaca a

Setelah membaca simbol a, kedudukan mesin = q3, menulis b dan

bergerak ke kanan.

Hasil sebagai berikut :

Gambar 2.2 Posisi mesin setelah membaca simbol a

Contoh 2.1

Dimiliki mesin turing dengan definisi M={ Q, ,, S,F,b, δ }

Q={q1,q2}

= {a,b}

= {a,b, b }

S={ q1}

F={ q2}

δ : δ (q1,a)= (q1,a,R)

δ (q1,b)= (q1,a,R)

δ (q1, b)= (q2, b ,L)

Pada state awal q1, bila mesin membaca a, maka ia tetap di q1,

kemudian menulis a dan gerak ke kanan.

Bila membaca b tetap q1 , menulis a dan bergerak kekanan.

Jika membaca blank kedudukan jadi q2 dan bergerak ke kiri.

Dengan demikian apabila diberikan umpan deretan string yang terdiri

dari deretan a dan b maka hasil adalah sederatan a dan kedudukan akhir

adalah q2 yang merupakan kedudukan final.

Berikut ini gerakan mesin tersebut apabila diberi masukan string : abbba

9

Gambar 2.3 Gerakan mesin ketika membaca abbba

Dapat dinyatakan bahwa mesin turing tersebut apabila diumpankan

sederetan symbol a dan atau simbol b dengan jumlah 0 atau lebih akan

mengantar pada kedudukan final q2. Dengan kata lain mesin turing

tersebut dapat mengenali bahasa (a,b)*.

1.2.4. Deskripsi Sesaat untuk gerakan Mesin Turing

Gerakan mesin tergantung pada kedudukan awal, simbol yang

dibaca, simbolyang ditulis dan gerakan posisi tulis/baca maka diskripsi

sesaat dapat diekspresikandengan menggunakan simbol sebagai berikut :

(q1,abbba) : mesin pada kedudukan q1 dan siap membaca simbol a

(digaris bawah)

Deskripsi sesaat mesin turing contoh 2.1. membaca: ‘abbba’ :

(q1,abbba)

|-- (q1,abbba)

|-- (q1,aabba)

|-- (q1,aaaba)

|-- (q1,aaaaa)

|-- (q1,aaaaab)

10

|-- (q2,aaaaa b) Final state

Deskripsi sesaat dapat juga dengan cara pemisahan string yang telah

dibaca dan yang belum dibaca dengan ekspresi :

qiw |-- w1qjw2

qi : kedudukan saat ini dan w = string yang akan dibaca, qj = kedudukan

baru setelah membaca simbol dan w1= substring yang telah dibaca dan

w2 = substring yang belum dibaca.

Pembacaan string ‘abbba’ dapat dituliskan deskripsi sesaat:

q1abbba

|-- aq1bbba

|-- aaq1bba

|-- aaaq1ba

|-- aaaaq1a

|-- aaaaaq1b

|-- aaaaaq2 (final state)

1.2.5. Mesin Turing Sebagai Pengenal Bahasa

Apabila M={ Q, , , S, F,b, δ } adalah suatu mesin turing, maka bahasa

yang dikenali oleh mesin turing tersebut dapat diungkapkan sebagai

himpunan dengan syarat sebagai berikut :

L(M)={w * | q1w |-- w1pw2 dengan pF dan wi *}

Ungkapan tersebut mengandung makna bahwa mesin turing M dikatakan

dapat mengenali bhasa L, atau L fungsi dari M, yaitu L(M) : himpunan

string dalam bahasa L berisi string-string w sedemikian sehingga jika

mesin turing semula dalam kedudukan q1 setelah membaca w dan

mengikuti gerakan yang ditentukan mesin M tersebut maka ia akan

mengantar mesin M ke kedudukan p, dengan p adalah kedudukan final

dalam mesin M.

Contoh

Tentukan bahasa yang dikenali oleh mesin turing berikut :

Mesin Turing dengan Q={q1,q2}, S={q1}, F={q2} dan δ berikut :

δ (q1,a)=(q1,a,R)

11

δ (q1, b) =(q2, b,R)

Jawab : uji dengan pemasukan :

b hasil q2

a hasil q2

aa hasil q2

aaa hasil q2

Kesimpulan :

Mesin tersebut menerima : b,a,aa,aaa,... atau {a*}

Contoh 2.2

Bahasa seperti apakah yang dikenali oleh mesin turing berikut ini :

M={ Q, , , S,F,b, δ }

Q={q1,q2,q3,q4,q5}

= {a,b}

= {a,b,c,d, b }

S={q1}

F={q5}

δ:

δ (q1,a)= (q2,c,R)

δ (q2,a)= (q2,a,R)

δ (q2,d)= (q2,d,R)

δ (q2,b)= (q3,d,L)

δ (q3,d)= (q3,d,L)

δ (q3,a)= (q3,a,L)

δ (q3,c)= (q1,c,R)

δ (q1,d)= (q4,d,R)

δ (q4,d)= (q4,d,R)

δ (q4,b)= (q5, b ,L)

Jawab :

mesin tersebut mengenali bahasa : { an bn | n>=1 }.

Untuk mendemonstrasikan gerakan mesin turing saat membaca string

dari bahasa tersebut dapat diujikan dengan disuruh membaca

12

string :’aaabbb’. Gerakan mesin dapat diikuti dari deskripsi sesaat

sebagai berikut :

(q1,aaabbb )

|-- (q2,caabbb)

|-- (q2,caabbb)

|-- (q2,caabbb)

|-- (q2,caabbb)

|-- (q3,caadbb)

|-- (q3, caadbb)

|-- (q3, caadbb)

|-- (q3, caadbb)

|-- (q1, caadbb)

|-- (q2, ccadbb)

|-- (q2, ccadbb)

|-- (q2, ccadbb)

|-- (q3, ccaddb)

|-- (q3, ccaddb)

|-- (q3, ccaddb)

|-- (q1, ccaddb)

|-- (q2, cccddb)

|-- (q2, cccddb)

|-- (q2, cccddb)

|-- (q3, cccddd)

|-- (q3, cccddd)

|-- (q3, cccddd)

|-- (q3, cccddd)

|-- (q1, cccddd)

|-- (q1, cccddd)

|-- (q1, cccddd)

|-- (q1, cccdddb)

|-- (q5, cccdddb)

=FINAL STATE

1.2.6. Loop yang Terus Menerus pada Mesin Turing

Jika diperhatikan bahwa suatu mesin turing dapat memiliki transisi yang

mengatur perilaku mesin sehingga dapat bergerak ke-kanan atau ke kiri,

maka dimungkinkan ada suatu mesin yang aturan transisinya justru

menyebabkan gerakan tersebut berulang terus menerus tidak dapat

berhenti. Perhatikan mesin turing berikut :

M={ Q, ,, S,F,b, δ }

Q={q1,q2,q3}

= {a,b}

= {a,b, b }

S={q1}

F={q3}

δ : δ (q1,a)= (q2,a,R)

δ (q1,b)= (q2,b,R)

δ (q1,b)= (q3, b,R)

δ (q2,a)= (q1,a,L)

δ (q2,b)= (q1,b,L)

δ (q2,b)= (q3, b,L)

Jika dicoba diinputkan string : ‘aaaa’ maka gerakan mesin adalah :

13

(q1,aaaa)

|-- (q2,aaaa)

|-- (q1,aaaa)

|-- (q2,aaaa)

|-- (q1,aaaa)

|-- ....

mesin akan terus bergerak ke kanan dan ke kiri sepanjang state q1 dan q2

dan tidak pernah sampai pada state final q3.

Jika dicoba diinputkan string : ‘bbaa’ maka gerakan mesin adalah :

(q1,bbaa)

|-- (q2,bbaa)

|-- (q1,bbaa)

|-- (q2,bbaa)

|-- (q1,bbaa)

|-- ....

Ternyata untuk masukan ini juga mesin turing bergerak terus tidak ada

akhirnya. Kalau dicermati dalam definisi gerakan di atas dapat

disimpulkan bahwa jika mesin turing diberi string ‘aa’, ‘bb’,’ba’ dan ‘ab’

mesin terus bergerak “bolak balik” dari karakter pertama ke karakter

kedua ketika membaca string. Hal ini menyebabkan string apapun yang

diberikan akan menyebabkan gerakan “bolak balik” itu selalu terjadi,

sehingga mesin turing tidak akan pernah mencapai kedudukan final.

Tentunya sebagai pengenal bahasa definisi mesin turing seperti tersebut

di atas perlu dihindari. Sehingga dalam mendifinisikan suatu mesin

turing harus ada jaminan dalam definisi gerakan mesin turing bahwa

tidak ada definisi fungsi gerakan mesin yang jika diberikan umpan string

menyebabkan mesin bergerak secara “loop”, berputar tidak pernah

sampai kedudukan final.

14