Teori Bahasa dan Otomata 1

Teori Bahasa dan Otomata

1

KATA PENGANTAR Teori Bahasa dam Otomata merupakan matakuliah wajib yang harus diambil oleh seluruh mahasiswa jurusan Teknik Indonesia di lingkungan Sekolah Tinggi Teknologi Indonesia. Matakuliah ini nantinya akan menjadi matakuliah prasyarat ketika akan mengambil matakuliah teknik kompilasi. Penulis mencoba menulis sesederhana mungkin dengan tujuan agar pembaca mudah mengerti atau memahami seluruh bahasan materi dalam modul teori bahasa dan otomata ini. Teori bahasa dan otomata dapat dikatakan sebagai bagian dari ilmu informatika klasik. Dalam modul ini akan banyak studi kasus yang diharapkan dapat membantu pembaca untuk memahami konsep yang dibahas dalam materi dalam bahasa dan otomata. Penulis menyadari masih terdapat kekurangan dalam penulisan modul ini. Penulis ingin menyampaikan ucapkan terimakasih kepada : 1. Bapak Jajang Kusnendar, MT yang telah memberikan perkuliahan teori bahasa dan otomata ketika penulis menempuh program sarjana pada Sekolah Tinggi Ilmu Manajemen dan Komputer Bandung 2. Sekolah Tinggi teknologi Indonesia Tanjungpinang yang bersedia mencetak/ memperbanyak modul ini 3. Pihak-pihak yang tidak dapat disebutkan satu persatu yang telah membantu dalam pembuatan modul ini Saran dan kritik dari pembaca sangat penulis tunggu dan dapat dikirm melalui e-mail penulis : [email protected] Akhir kata, semoga modul ini dapat bermanfaat bagi para pembaca. Khususnya pembaca yang sedang mengambil matakuliah teori bahasa dan otomata. Selamat belajar.

Tanjungpinang, 25 Juni 2014

Dwi Nurul Huda Teori Bahasa dan Otomata

2

DAFTAR ISI KATA PENGANTAR DAFTAR ISI BAB 1 PENGANTAR TEORI BAHASA DAN OTOMATA BAB 2 FINITE STATE AUTOMATA BAB 3 EKUIVALENSI NFA KE DFA BAB 4 NFA DENGAN ε-MOVE BAB 5 EKSPRESI REGULER BAB 6 ATURAN PRODUKSI UNTUK SUATU FINITE STATE AUTOMATA BAB 7 FINITE STATE AUTOMATA DENGAN OUTPUT (MESIN MOORE) BAB 8 POHON PENURUNAN BAB 9 PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS


3

BAB 1 PENDAHULUAN Ilmu komputer memiliki dua komponen utama yaitu model dan gagasan tentang komputasi dan teknik rekayasa untuk perancangan sistem komputasi (perangkat keras dan perangkat lunak). Teori bahasa dan otomata masuk kedalam komponen utama dalam ilmu komputer. Teori bahasa dan otomata diterapkan pada beberapa perancangan digital seperti pada pmbuatan bahas apemrograman dan kompilator. Sedangkan tujuan mempelajari Teori Bahasa dan Otomata sendiri yaitu mengajarkan dasar-dasar teori bahasa formal dan modelmodel mesin matematis yang menggambarkan prinsip kerja komputer. Otomata merupakan suatu bentuk (model matematika) yang memiliki fungsi-fungsi dari komputer digital yaitu menerima input, menghasilkan output, bisa memiliki penyimpanan sementara dan mampu membuat keputusan dalam mentransformasikan input ke output. Input pada mesin otomata dianggap sebagai bahasa yang harus dikenali oleh mesin. Selanjutnya mesin otomata akan membuat keputusan yang mengindikasikan apakah input ini diterima atau tidak. Otomata bisa digunakan untuk memodelkan hardware. Umumnya kita hanya tahu bahasa alami yaitu bahasa inggris atau bahasa indonesia. Sebuah bahasa merupakan himpunan string-string dari simbol-simbol untuk suatu alphabet. String sendiri merupakan suatu kata (gabungan dari huruf) dalam bahasa, contoh string adalah ‘Tanjungpinang‘. String juga dapat bernilah kosong dan biasa dilambangkan menggunakan simbol ε. Contoh penerapan mesin otomata, misalnya kita akan memodelkan mesin otomata yang hanya dapat menerima inputan dalam bahasa inggris. Apabila digambarkan pemodelan bahasanya akan menjadi : Teori Bahasa dan Otomata

4

a

q4

q5

n

q6

g

q0

d

q1

e

q2

n

q3

y

q7 q4

t i

q8

q9

s

q10

t

q11 q4

Gambar 1.1 Mesin Otomata Penerima Input Bahasa Inggris

Pada gambar 1.1 diatas merupakan mesin otomata yang hanya dapat menerima inputan berupa bahasa inggris, jika mesin mendapatkan string inputan :  dengan

: di tolak

 deny

: diterima

 dentist

: diterima

suatu string dikatakan diterima apabila mencapai state akhir(lingkaran ganda) untuk kasus ini ada pada q7 dan q11. State awal selalu diawali oleh panah tanpa inputan (state q0).

HIRARKI CHOMSKY Tata Bahasa (grammar)

didefinisikan sebagai kumpulan dari himpunan-himpunan

variable, simbol-simbol terminal, simbol awal yang dibatasi oleh aturan produksi. Pada tahun 1959, Noam Chomsky menggolongkan tingkatan bahasa menjadi empat yang disebut sebagai Hirarki Chomsky. Penggolongan Hirarki Chomsky : Tabel 1.0 Penggolongan Bahasa Bahasa Regular/Tipe 3

Mesin Otomata

Batasan Aturan Produksi

Finite State Automata (FSA) :

α merupakan sebuah simbol

1. Deterministic Automata (DFA)

Finite variable β maksimal memiliki sebuah

2. Non- Deterministic Finite simbol variable yang bila ada Automata (NFA)

terletak diposisi paling kanan Teori Bahasa dan Otomata

5

Bahasa Bebas

Mesin Otomata

Batasan Aturan Produksi

Konteks/Context Push Down Automata (PDA)

α

Free/Tipe2

berupa sebuah simbol

variable

Context Sensitive/Tipe1

Linier Bounded Automata

|α | ≤ |β|

Unrestricted/Phase

Mesin Turing

Tidak ada batasan

Structure/Natural Language/Tipe 0 Aturan produksi merupakan pusat dari tata bahasa yang menspesifikasikan bagaimana suatu tata bahasa melakukan transformasi dari suatu string ke bentuk lainnya dan melalui aturan produksi tersebut didefinisikan suatu bahasa yang berhubungan dengan tata bahasa tersebut.

Suatu aturan produksi dapat dinyatakan dalam bentuk α→β ( dibaca : α

menghasilkan β atau dibaca : α menurunkan β). Suatu α menyatakan simbol-simbol pada ruas kiri aturan produksi. Sedangkan β menyatakan simbol-simbol pada ruas kanan aturan produksi. Beberapa istilah dalam aturan produksi : 1. Simbol variable/nonterminal :

simbol

yang

masih

dapat

diturunkan, biasanya

dilambangkan menggunakan abjad capital. 2. Simbol terminal

:

simbol yang tidak dapat diturunkan kembali, biasanya

dilambangkan menggunakan abjad non-capital(huruf kecil). Contoh penerapan tata bahasa “Noam Chomsky” : Table 2.0 Contoh Tata Bahasa Berdasarkan Penggolongan Noam Chomsky Bahasa

Contoh

Regular/Tipe 3

A→b

Bebas Konteks/Context Free/Tipe2

B → bcA

Context Sensitive/Tipe1

B → Abcd

Unrestricted/Phase Structure/Natural

AbC → abC

Language/Tipe 0


6

LATIHAN SOAL Buatlah masing-masing 5 buah contoh tata bahasa yang memenuhi aturan tata bahasa : 1. Regular 2. Bebas Konteks 3. Context Sensitive 4. Unrestricted


7

BAB 2 FINITE STATE AUTOMATA Finite State Automata atau yang dikenal dengan istilah FSA merupakan suatu model mesin otomata dari bahasa reguler. Suatu Finite State Automata dapat memiliki state banyak berhingga yang dapat berpindah-pindah dari suatu state ke state lainnya. Jenis otomata ini tidak memiliki tempat penyimpanan, sehingga kemampuan mengingatnya terbatas. Contoh penerapan Finite State Automata (Pengecek parity ganjil):

0 q0

0 1

q1 1

Gambar 2.0 Contoh Penerapan FSA

1. Pengirim akan menambahkan bit paritas sehingga jumlah bit 1 adalah ganjil. Misal, terdapat data : 0110  Pengirim akan menambahkan bit 1, sehingga :  Penerima akan memperoleh : 01101 2. Bila suatu saat penerima memperoleh jumlah bit 1 yang genap, misalnya : 10010, maka penerima akan memutuskan telah terjadi kesalahan/ error dalam pengiriman. Beberapa hal yang harus diketahui berkenaan dengan symbol gambar sebelum memulai materi FSA (Finite State Automata) adalah : 1. Lingkaran menyatakan state/kedudukan 2. Label pada lingkaran merupakan nama state 3. Busur menyatakan transisi, yaitu perpindahan state/kedudukan Teori Bahasa dan Otomata

8

4. Label pada busur merupakan simbol input 5. Lingkaran diawali sebuah busur tanpa label yang artinya state awal 6. Lingkaran ganda menyatakan state akhir/final state

PENERAPAN FINITE STATE AUTOMATA Secara formal FSA dinyatakan menggunakan beberapa symbol : •

Q = himpunan state

•

∑ = himpunan simbol input

•

δ = fungsi transisi

•

S = state awal

•

F = himpunan state akhir

Contoh misalkan pada gambar pengecek pariti ganjil berikut :

0 q0

0 1

q1 1

Gambar 2.1 Contoh Penerapan FSA

Apabila dinyatakan menggunakan symbol, maka : •

Q = {q0,q1}

•

∑ = {0,1}

•

δ = fungsi transisi δ

0

1

q0

{q0}

{q1}

q1

{q0}

{q0}

•

S = q0

•

F = {q1}


9

FSA dibagi menjadi dua macam, yaitu DFA( Deterministic Finite Automata ) dan NFA ( NonDeterministic Finite Automata ).

.TEST . TEST . TEST . TEST . TEST . TEST .

Berdasarkan gambar diatas, tentukan : •

Q=?

•

∑=?

•

δ=?

•

F=?

TEST . • S=? TEST .


10

A. DETERMINISTIC FINITE AUTOMATA / DFA Deterministic Finite Automata merupakan bagian dari FSA. Deterministic Finite Automata/DFA maksudnya dari suatu state ada tepat satu state berikutnya untuk setiap simbol masukan yang diterima. Contohnya :

•

Q = {q0,q1,q2}

•

∑ = {a,b}

•

S = q0

•

F = {q2}

Suatu fungsi transisi bisa di bentuk menjadi 2 bentuk :

δ

a

b

q0

{q0}

{q1}

q1

{q1}

{q2}

q2

{q1}

{q2}


11

B. NON-DETERMINISTIC FINITE AUTOMATA / NFA Non-Deterministic Finite Automata merupakan bagian dari FSA. Non-Deterministic Finite Automata/NFA maksudnya Dari suatu state bisa terdapat 0, 1 atau lebih busur keluar (transisi) berlabel simbol input yang sama. Contohnya :

•

Q = {q0,q2}

•

∑ = {a,b}

•

S = q0

•

F = {q2} δ

a

b

q0

{q0,q2}

{q2}

q2

{q2}

{q2}

Dari state q0 ketika memperoleh inputan yang sama yaitu a dapat menuju ke lebih dari 1 state yaitu {q0,q2}

.ANALISIS. Apa Perbedaan Antara Deterministic Finite Automata/DFA dan Non-Deterministic Finite Automata/NFA ????

TEST . TEST .


12

EKUIVALENSI ANTAR DFA Dalam suatu Deterministic Finite Automata/DFA suatu mesin dapat di gambarkan berbeda tetapi tetap memiliki outputan yang sama. Contoh mesin DFA : a

q0

Gambar 2.2 DFA Mesin 1

a

q0

a

q1

Gambar 2.3 DFA Mesin 2

Berdasarkan gambar diatas dapat diambil kesimpulan bahwa walaupun kedua gambar DFA diatas bebeda tetapi hasil output yang diterimanya tetap sama yaitu hanya dapat menerima inputan yang mengandung a.


13

.SOAL LATIHAN. Gambarkan FSA (Finite State Automata) berikut ini kemudian analisis apakah FSA (Finite State Automata) tersebut termasuk DFA (Deterministic Finite Automata) atau NFA (NonDeterministic Finite Automata) disertai dengan 3 buah contoh string yang diterima dan 3 buah contoh string yang ditolak : 1. Q = {q0,q1,q2} Σ = {0,1} S = {q0} F = {q2}

TEST . δ

0

1

q0

{q1}

{q2}

{q2}

{q2}

{q1}

-

TEST . q1 q2

2. Q = {q0,q1,q2,q3,q4} Σ = {a,b} S = {q0} F = {q2,q4} δ

a

b

q0

{q0,q3}

{q0,q1}

q1

-

{q2}

q2

{q2}

{q2}

q3

{q4}

-

q4

{q4}

{q4}


14

BAB 3 EKUIVALENSI NON-DETERMINISTIC FINITE STATE AUTOMATA (NFA) KE DETERMINISTIC FINITE STATE AUTOMATA(DFA) Ekuivalen artinya sama, pada bahasan materi ini artinya dapat menerima string yang sama baik itu menggunakan mesin Non-Deterministc Finite Automata (NFA) maupun Deterministc Finite Automata (DFA). Sebuah mesin Non-Deterministc Finite Automata (NFA) dapat dibuat menjadi mesin Deterministic Finite Automata(DFA) yang dapat menerima string yang sama. Ada beberapa tahap yang dapat ditempuh untuk melakukan ekuivalensi Non-Deterministc Finite Automata (NFA) ke Deterministc Finite Automata (DFA) : 1. Buat tabel transisi dari Non-Deterministc Finite Automata (NFA) 2. Telusuri state berikutnya dengan memanfaatkan tabel transisi ditambah dengan state { } 3. Tentukan finish baru jika ada, dengan melihat seluruh state yang mengandung finish awal. Contoh kasus diberikan gambar Non-Deterministc Finite Automata (NFA) berikut : Diketahui : Q = {qo,q1}

0

Σ = {0,1} S = q0

q0

0,1

q1

F = {q1}


15

Ditanyakan : Buatlah Deterministic Finite Automata yang ekuivalen dengan Non-Deterministic Finite Automata diatas. Jawab : 1. Buat tabel transisi dari Non-Deterministc Finite Automata (NFA) δ

0

1

q0

{q0,q1}

{q1}

q1

{}

{}

State baru yang terbentuk dan akan ditelusuri

2. Telusuri state berikutnya dengan memanfaatkan tabel transisi ditambah dengan state { } δ

0

1

q0

{q0,q1}

{q1}

q1

{}

{}

{ q0,q1}

{q0,q1}

{q1}

{}

{}

{}

3. Tentukan finish baru jika ada, dengan melihat seluruh state yang mengandung finish awal.

Finish Baru

δ

0

1

q0

{q0,q1}

{q1}

q1

{}

{}

{ q0,q1}

{q0,q1}

{q1}

{}

{}

{}


16

4. Gambar Deterministic Finite Automata : 0,1

1

q0 0

{q0,q1} q0

q1

0,1

{}

1 0


17

.SOAL LATIHAN. 1. Buatlah deterministic Finite Automata yang ekuivalen dengan Non-Deterministic Finite Automata berikut : Q = {qo,q1,q2,q3} Σ = {a,b} S = q0 F = {q3} Fungsi Transisinya sebagai berikut : δ

TESTq0 . q1

TESTq2 . q3

a

b

{q0,q1}

q1

q3

q3

q4

{}

q4

q4

2. Buatlah deterministic Finite Automata yang ekuivalen dengan Non-Deterministic Finite Automata berikut : Q = {p,q,r} Σ = {0,1} S=p F = {q} Fungsi Transisinya sebagai berikut : δ

0

1

p

q

{}

q

{q,r}

r

r

p

{q,r}


18

BAB 4 NON-DETERMINISTIC FINITE STATE AUTOMATA (NFA) DENGAN ε-Move Suatu gambar Non-Deterministc Finite Automata (NFA) yang mengandung ε-Move ( ε dapat dianggap “empty” artinya dapat tidak dibaca inputannya atau diperbolehkan langsung menuju state berikutnya tanpa membaca inputan ε). Contoh gambar Non-Deterministic Finite Automata mengandung ε-Move : 0,1

q0

ε

q1

0

ε

q2

q3 q0

1

Berdasarkan gambar diatas maka dapat di ambil kesimpulan :

 Dari q0 tanpa membaca input dapat langsung berpindah ke state q1  Dari q2 tanpa membaca input dapat langsung berpindah ke state q3 Kegunaan transisi ε ini adalah memudahkan dalam mengkombinasikan Finite State Automata.

.ε

– CLOSURE UNTUK SUATU NON-DETERMINISTIC FINITE AUTOMATA DENGAN ε-MOVE.

ε–closure merupakan himpunan state-state yang dapat dicapai dari suatu state tanpa membaca input. ε–closure sendiri dapat disingkat nantinya menjadi ε–cl. Contoh pada gambar berikut :

TEST . TEST .


19

0

q0

ε

0

q1

ε

q2

q3 q0

1

Berdasarkan gambar diatas, maka dapat di buat ε–closure nya sebagai berikut :

 ε–closure (q0) = {q0,q1}  ε–closure (q1) = {q1}  ε–closure (q2) = {q2,q3}  ε–closure (q3) = {q3} . LATIHAN .

Buatlah ε–closure dari gambar Non-Deterministic Finite Automata(NFA) berikut : q4 ε q0

ε

q1

ε

q2

0 0

q3 q0 1

.

EKUIVALENSI NON-DETERMINISTIC FINITE AUTOMATA DENGAN ε-MOVE KE NON-DETERMINISTIC FINITE AUTOMATA TANPA ε-MOVE

.

Dari suatu Non-Deterministic Finite Automata dengan ε – Move dapat dibuat ekuivalensinya menjadi Non-Deterministic Finite Automata tanpa ε – Move. Langkah-langkah melakukan ekuivalensi Non-Deterministic Finite Automata dengan ε – Move menjadi NonDeterministic Finite Automata tanpa ε – Move :

TEST .

1. Buat tabel transisi Non-Deterministic Finite Automata yang mengandung ε – Move TEST .

2. Tentukan ε- closure untuk setiap state Teori Bahasa dan Otomata

20

3. Carilah setiap fungsi transisi hasil perubahan Non-Deterministic Finite Automata ε – Move ke Non-Deterministic Finite Automata tanpa ε – Move dengan menggunakan rumus : δ' (state,input) = ε – closure ( δ (ε – closure(state),input))

4. Buat table transisi baru dari hasil perolehan yang sudah dilakukan pada point(3) 5. Tentukan Final State dengan melihat state-state pada ε –closure yang menuju pada state finish semula . CONTOH .

Buatlah NFA tanpa ε- Move yang ekuivalen dengan NFA dengan ε – Move berikut ini : 0

q0

ε

q1

0

ε

q2

q3 q0

1

Langkah –langkah :

1. Buat tabel transisi Non-Deterministic Finite Automata yang mengandung ε – Move δ

0

1

q0

{}

{}

q1

q2

{}

q2

{}

{}

q3

q3

q1

2. Tentukan ε- closure untuk setiap state ε–closure (q0) = {q0,q1} ε–closure (q1) = {q1} ε–closure (q2) = {q2,q3} ε–closure (q3) = {q3}


21

3. Carilah setiap fungsi transisi hasil perubahan Non-Deterministic Finite Automata ε – Move ke Non-Deterministic Finite Automata tanpa ε – Move dengan menggunakan rumus : δ' (state,input) = ε – closure ( δ (ε – closure(state),input)) δ' (q0,0)

=

ε – cl ( δ (ε – cl (q0),0)) ε – cl ( δ{q0,q1},0) ε – cl ({q2}) { q2,q3}

δ' (q0,1)

=

ε – cl ( δ (ε – cl (q0),1)) ε – cl ( δ{q0,q1},1) ε – cl ({}) {}

δ' (q1,0)

=

ε – cl ( δ (ε – cl (q1),0)) ε – cl ( δ{q1},0) ε – cl ({q2}) {q2,q3}

δ' (q1,1)

=

ε – cl ( δ (ε – cl (q1),1)) ε – cl ( δ{q1},1) ε – cl ({}) {}

δ' (q2,0)

=

ε – cl ( δ (ε – cl (q2),0)) ε – cl ( δ{q2,q3},0) ε – cl ({q3}) {q3}

δ' (q2,1)

=

ε – cl ( δ (ε – cl (q2),1)) ε – cl ( δ{q2,q3},1) ε – cl ({q1}) {q1}

δ' (q3,0)

=

ε – cl ( δ (ε – cl (q3),0)) ε – cl ( δ{q3},0) ε – cl ({q3}) {q3}


22

δ' (q3,1)

=

ε – cl ( δ (ε – cl (q3),1)) ε – cl ( δ{q3},1) ε – cl ({q1}) {q1}

4. Buat table transisi baru dari hasil perolehan yang sudah dilakukan pada point(3) δ

0

1

q0

{q2,q3}

{}

q1

{q2,q3}

{}

q2

q3

q1

q3

q3

q1

5. Tentukan Final State dengan melihat state-state pada ε –closure yang menuju pada state finish semula Finis semula ada di q3, sehingga lihat state ε –closure yang menuju pada state q3 ε–closure (q0) = {q0,q1} ε–closure (q1) = {q1} ε–closure (q2) = {q2,q3} ε–closure (q3) = {q3} Berdasarkan ε–closure diatas maka dapat diperoleh state Finish lain selain q3 yaitu q2, sehingga final state sekarang ada 2 yaitu state q2 dan state q3. Gambar Non-Deterministic Finite Automata tanpa ε-Move :

δ

0

1

q0

{q2,q3}

{}

q1

{q2,q3}

{}

q2

q3

q1

q3

q3

q1

0 0

q0

0 0

q1

0

q2 1

q3 q0

0 1


23

.SOAL LATIHAN. Buatlah NFA tanpa ε- Move yang ekuivalen dengan NFA dengan ε – Move berikut ini : q4 ε q0

ε

q1

ε

q2

0 0

q3 q0 1

TEST . TEST .


24

BAB 5 EKSPRESI REGULER Suatu Finite State Automata dapat dinyatakan menggunakan Ekspresi Regular (ER). Ekspresi Reguler dapat membuat suatu pola untuk suatu untai/string dari suatu bahasa. Beberapa notasi dalam Ekspresi reguler : No 1

Simbol

Keterangan

* (karakter asterik)

String yang dapat dibangkitkan

Artinya bisa tidak muncul bisa ER : a* → a,aa,aaa,... juga muncul berkali-kali (0-n)

2

3

ER : ab*c → ac, abc, abbc, ....

+ (ditulis pada posisi

Artinya minimal muncul satu kali ER : 𝑏 + → b, bb, bbb,...

diatas/superscript)

(1-n)

ER : 𝑎𝑏 + → ab,abb,abbb,...

+ atau  (tanda plus)

Artinya dapat dipilih salah satu

ER : a  b → a, b

.HUBUNGAN

ANTARA EKSPRESI REGULER DENGAN FINITE STATE AUTOMATA.

Suatu Ekspresi Reguler dapat digambarkan kedalam bentuk Finite State Automata begitu pula sebaliknya. Contoh transformasi dari ER(Ekspresi Reguler) Ke Finite State Automata : No 1

Contoh ER ER : ab*c

Finite State Automata TEST . b

TEST . a

q0

2

c

q1

q2 q0

ER : 𝑎𝑏 +

b

q0

a

q1

b

q2 q0


25

No 3

Contoh ER

Finite State Automata

ER : a  b q0

a,b

q1 q0

Contoh transformasi dari Finite State Automata ke ER(Ekspresi Reguler) : No

Contoh Finite State Automata

1

ER (Ekspresi Reguler)

c a

q0

2

b

q1

c

a

q0

3

b

ER : abc*

q2 q0

q1

c

q2 q0

ER: a ∗ b𝑐 +

a

q0

b,c

q0 q1

ER : a*(b  c)


26

.SOAL LATIHAN. 1. Buatlah string yang dapat dibangkitkan dari ER berikut : a. ER : ab*cd b. ER : 𝑎𝑏 + cd c. ER : 𝑎𝑏 + 𝑐𝑑∗ d d. ER : (a  b)ab 2. Gambarkan FSA dari ER berikut : a. ER : 𝑎𝑏 + 𝑐𝑑∗ d b. ER : (a  b)ab

TEST 3. Tuliskan . ER dari FSA berikut : a.

a

TEST . a

q0

b.

q1

0 q0

0 1

q1 1


27

BAB 6 ATURAN PRODUKSI UNTUK SUATU FINITE STATE AUTOMATA

.ATURAN

PRODUKSI BAHASA REGULER .

Sebuah otomata berhingga dapat menspesifikasikan suatu bahasa sebagai himpunan semua untai yang menggerakannya dari state awal hingga ke state akhir. Masih ingat materi pada bab 1??? Aturan Produksi pada bahasa regular TEST: α. → β ( dibaca α menghasilkan β )

Keterangan :

TEST .

α : Sebuah symbol variable β : Maksimal memiliki sebuah symbol variable, yang bila ada terletak dipaling kanan Ulasan pada bab 1 : 

Symbol variable atau disebut juga symbol non-terminal ialah symbol yang masih dapat diturunkan. Biasanya di definisikan menggunakan huruf besar.



Simbol terminal aialah simbol yang sudah tidak dapat diturunkan kembali. Didefinisikan menggunakan huruf kecil.

Suatu bahasa / grammar didefinisikan dengan 4 tupel, yaitu : V

: himpunan symbol variable/non-terminal

T

: himpunan symbol terminal

P

: kumpulan aturan produksi

S

: symbol awal


28

.MENGKONSTRUKSI

ATURAN PRODUKSI DARI SUATU FSA .

Ada beberapa hal yang harus diperhatikan ketika anda akan mengkonstruksi suatu FSA(Finite State Automata) terutama state yang akan menuju final state/ state akhir. Contoh gambar FSA(Finite State Automata) : TEST . b

TEST .

q4 ε

q0

a

q1

ε

q2

a

q3 q0

Dari gambar diatas dapat diketahui bahwa mesin FSA(Finite State Automata) tersebut memiliki inputan ‘a‘ dan ‘b‘ dan akan menjadi simbol terminal pada aturan produksi yang akan dibuat. Misalnya state awal kita simbolkan dengan S (state awal) yaitu q0. Dari q0 mendapat inputan ‘a’ langsung menuju ke state q1. Aturan produksinya dapat ditulis sbb : S → aA Dimana A diidentikan dengan q1 (bagian yang belum terbangkitkan mulai dari state q1). Dari q1 mendapatkan inputan transisi-ε (tanpa menerima input) menuju ke q2. Aturan produksinya dapat ditulis sbb : A→B B diidentikan sebagai q2. Dari q2 memperoleh inputan a ke q3 dan inputan transisi-ε (tanpa menerima input) menuju ke q4. Aturan produksinya dapat ditulis sbb : B→a B→C Dimana C diidentikan sebagai q4. Dari q4 mendapat inputan inputan b menuju state q1. C → bA


29

Aturan produksi diatas dapat dituliskan kembali sbb : S → aA A→B B→a|C C → bA Secara formal tata bahasa yang diperoleh dari mesin FSA(Finite State Automata) dapat dituliskan sbb : V = {S, A, B, C} T = {a,b} P = { S → aA , A → B, B → a | C, C → bA} S=S

.MENGKONSTRUKSI

SUATU FSA DARI SUATU ATURAN PRODUKSI.

Jika sebelumnya dari suatu FSA dapat di konstruksi bentuk aturan produksinya, sekarang adalah kebalikannya. Dari suatu aturan produksi dapat digambarkan FSA-nya. Contoh apabila terdapat aturan produksi berikut : S → aS | bA | a

TEST .

A → cB

TEST .

B → aS Gambar FSA dari aturan tersebut adalah sbb : a a

q0

b

c

q1

q2

q3 q0

a


30

.SOAL LATIHAN. 1. Diberikan gambar FSA (Finite State Automata) berikut : q4 b

q0

a

q1

ε

ε q2

b

q3 q0

a

Buatlah aturan produksi untuk gambar FSA(Finite State Automata) diatas !!!

TEST . aturan produksi berikut : 2. Diberikan S → baA | B |baB | ε

TEST .A → bS | a B → aS

Buatlah gambar FSA (Finite State Automata) dari aturan produksi tersebut !!!


31

BAB 7 FINITE STATE AUTOMATA DENGAN OUTPUT (MESIN MOORE) Pada mesin Moore suatu output akan berasosiasi dengan state. Mesin Moore dapat didefinisikan kedalam : Q : himpunan state Σ : himpunan symbol input δ : fungsi transisi S : state awal Δ : himpunan output λ : fungsi output untuk setiap state CATATAN  Final state dari suatu DFA (Deterministic Finite Automata) dihilangkan, karena keputusan dimunculkan sebagai output.

Contoh mesin Moore, missal ingin memperoleh sisa pembagian (Mod) suatu bilangan dengan 2. Dimana suatu inputan dinyatakan menggunakan bilangan biner. Maka diperoleh : Q

: {q0,q1}

Σ

: {0,1} – karena inputan akan diubah menjadi bilangan biner

S

: q0

Δ

: {0,1} --- karena kemungkinan sisanya jika tidak 0 berati 1

λ (q0) : 0 λ (q1) : 1 Teori Bahasa dan Otomata

32

Mesin Moore untuk Mod 2adalah sbb : 0

0

q0

1

q1

0

1

1

Implementasi ke dalam studi kasus : 1) 7 Mod 2 = ? 7 = 111, maka jika di masukan kedalam gambar diatas akan inputan terakhir akan berhenti di state q1 yang bernilai 1, sehingga dapat ditemukan bahwa 7 Mod 2 = 1 2) 12 Mod 2 = ? 12 = 1100, maka jika di masukan kedalam gambar diatas akan inputan terakhir akan berhenti di state q0 yang bernilai 0, sehingga dapat ditemukan bahwa 12 Mod 2 = 0


33

BAB 8 POHON PENURUNAN Pohon penurunan berguna untuk menggambarkan bagaimana memperoleh suatu string(untai) dengan cara menurunkan simbol-simbol variabel menjadi simbol-simbol terminal. Simbol variabel akan diturunkan sampai menjadi simbol terminal seluruhnya. Contoh: S → AB A → aA | a B → bB | b Berdasarkan tata bahasa bebas konteks diatas maka dapat digambarkan pohon penurunan untuk memperoleh untai ‘aabbb’ sebagai berikut :

S B

A a

A a

b

B

b

B b


34

Proses penurunan atau parsing dapat dilakukan dengan cara berikut : 1. Penurunan terkiri (leftmost derivation) : symbol variable terkiri yang diperluas terlebih dahulu 2. Penurunan terkanan (rightmost derivation) : symbol variable terkanan yang diperluas terlebih dahulu Contoh : S → AB A → aA | a B → bB | b Untai yang ingin diperoleh : ‘aabbb’ Penyelesaian : 1. Penurunan terkiri (leftmost derivation) S → AB → aAB → aaB → aabB → aabbB → aabbb 2. Penurunan terkanan (rightmost derivation) S → AB → AbB →AbbB → Abbb → aAbbb →aabbb Dalam pohon penurunan ada yang disebut Ambiguitas. Ambiguitas terjadi apabila terdapat lebih dari satu pohon penurunan yang berbeda tetapi untuk memperoleh untai yang sama. Contoh : S→A|B A → ab B → ab Untuk memperoleh untai yang sama yaitu ‘ab’, dapat digambarkan dua pohon penurunan yang berbeda tetapi untuk mencapai untai yang sama yaitu ‘ab’. S

S

atau

A a

B b

a

b


35

.SOAL LATIHAN. 1. Gambarkan pohon penurunan untuk memperoleh string ‘bbabbaab’ dari tata bahasa bebas konteks berikut : S → AA A → AAA |a |bA |Ab 2. Buktikan bahwa tata bahasa bebas konteks berikut ambigu : S → SaS | SbS |c Untuk untai : ‘cacbc’

TEST . TEST .


36

BAB 9 PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS Penyederhanaan tata bahasa bebas konteks bertujuan untuk melakukan pembatasan sehingga pohon penurunan tidak memiliki aturan produksi yang tidak berarti. Contoh : S→A A→B B→C C→D D→a|A Berdasarkan aturan produksi diatas terlihat beberapa aturan yang sebetulnya tidak perlu sebab akhirnya tetap berujung pada S → a, aturan produksi D → A juga menyebabkan kerumitan karena akan kembali lagi ke atas A → B. Tahap-tahap penyederhanaan tata bahasa bebas konteks : 1. Penghilangan produksi ε 2. Penghilangan produksi unit 3. Penghilangan produksi useless(tidak berguna)

.PENGHILANGAN

PRODUKSI ε.

Produksi ε adalah produksi dalam bentuk : α →ε atau dapat disebut produksi kosong (empty). Penghilangan produksi ε dapat dilakukan dengan mengganti produksi yang mengandung ε. Contoh kasus : TEST .

S → aBcd B → ab|ε

TEST .


37

Pada kasus diatas B bernilai nullable, maka penyederhanaannya menjadi : S → aBcd | acd B → ab

.PENGHILANGAN

PRODUKSI UNIT.

Produksi unit adalah suatu produksi dimana ruas sebelah kiri dan kanan aturan produksi hanya berupa sebuah simbol variabel, seperti A → B. Adanya kasus seperti itu membuat tata bahasa memiliki kerumitan tertentu. Contoh : S → Sa S→A A→B

Mengandung produksi Unit

TEST . TEST .

A → bb B → cd Aturan produksi diatas dapat dihilangkan produksi unitnya yaitu dengan cara mengganti aturan produksi yang mengandung produksi unit. S → Sa S → bb |cd A → bb|cd B → cd

.PENGHILANGAN

PRODUKSI USELESS.

Produksi useless merupakan suatu aturan produksi yang tidak berguna atau tidak terpakai, sehingga dapat dihilangkan. Produksi tersebut jika tidak dihilangkan tidak akan pernah terpakai karena tidak dapat mengalami penurunan apapun atau tidak akan mengalami penurunan hingga terminal. Contoh : S → aSa | Abc | Bcd

TEST . TEST .

A → aAb B → BBB | a Teori Bahasa dan Otomata

38

Berdasarkan aturan produksi diatas maka ada aturan produksi yang dapat dihilangkan yaitu : S → Abc A → aAb Sebab penurunan A tidak akan menuju symbol terminal, sehingga apabila tidak dihilangkan akan mengalami kerumitan tertentu. Sehingga berdasarkan aturan produksi tersebut dapat disederhanakan menggunakan penghilangan produksi useless menjadi : S → aSa | Bcd B → BBB | a Penyederhanaan tata bahasa bebas konteks harus melewati ketiga tahapan tersebut. Tidak ada yang boleh terlewatkan, walaupun nantinya bisa jadi dari suatu aturan produksi ada yang tidak mengandung produksi useless, ε ataupun unit.


39

.SOAL LATIHAN. 1. Hilangkan semua aturan produksi useless dari tata bahasa bebas konteks berikut : S → AD |BC A→b B → bD | a D → DB |AD 2. Hilangkan semua aturan produksi ε dari tata bahasa bebas konteks berikut : S→C

TEST .C → dC | ε D → bC

3. Hilangkan semua aturan produksi unit dari tata bahasa bebas konteks berikut : TEST . S → Aa | B B → A |bb A → a |bc|B 4. Sederhanakanlah tata bahasa bebas konteks berikut menggunakan aturan produksi ε, produksi unit dan produksi useless : S → AA| C |bd A → Bb | ε B → AB |d C → de


40

Teori Bahasa dan Otomata 1

Recommend Documents