Pengantar TBO. Pertemuan Ke-2. Sri Handayaningsih, S.T., M.T. Teknik Informatika

Pengantar TBO

Pertemuan Ke-2 Sri Handayaningsih, S.T., M.T. Email : [email protected] Teknik Informatika

1

TIU dan TIK Mengenal konsep bahasa dan otomata serta berbagai penerapannya, antara lain: a. Simbol, alfabet b. String dan operasi yang ada c. Bahasa dan Operasi yang ada d. star closure dan positif closure e. Bentuk Otomata f. Contoh Aplikasi

TEORI BAHASA OTOMATA

2

Computasi

CPU


memory

3

temporary memory input memory CPU output memory Program memory


4

Contoh:

f ( x ) x

3

temporary memory input memory CPU output memory

Program memory Compute 1

x x

Compute 2

x x


2

5

f ( x ) x temporary memory

3

input memory

x 2 CPU output memory

Program memory compute

x x

compute

x x


2

6

temporary memory

z 2 * 2 4 f ( x ) z * 2 8

f ( x ) x

3

input memory

x 2 CPU output memory

Program memory compute

x x

compute

x x


2

7

temporary memory

z 2 * 2 4 f ( x ) z * 2 8

f ( x ) x

3

input memory

x 2 CPU Program memory compute

x x

compute

x x


f ( x ) 8 output memory

2

8

Automaton temporary memory Automaton

input memory CPU output memory

Program memory


9

Perbedaan dari beberapa Otomata Perbedaan berdasarkan temporary memory • Finite Automata:

Tidak mempunyai

• Pushdown Automata:

Bentuknya Stack

• Turing Machines:

Pengaccessan memory secara random


10

Finite Automaton (FA) temporary memory

Finite Automaton

input memory output memory

Contoh: Mesin Pencari Kata (Kekuatan komputasi kecil) TEORI BAHASA OTOMATA

11

Pushdown Automaton (PDA) Stack

Pushdown Automaton

Push, Pop


Contoh : Compilers pada bahasa pemrograman (Kekuatan komputasi medium) TEORI BAHASA OTOMATA

12

Mesin Turing Random Access Memory

Turing Machine


Contoh : Banyak Algoritma (Kekuatan komputasi Tinggi) TEORI BAHASA OTOMATA

13

Power of Automata Dalam Menyelesaikan Permasalahan Finite

Pushdown

Mesin

Automata

Automata

Turing

Kekuatan rendah


Kekuatan tinggi

14

Bahasa


15

• Bahasa adalah kumpulan dari string • String : Kumpulan dari huruf – contoh: “cat”, “dog”, “house”, … – terdefinisi pada alphabet:

 a, b, c,, z


16

Alphabets and Strings • Alphabet menggunakan huruf kecil:

 a, b

• String

a ab abba baba aaabbbaabab TEORI BAHASA OTOMATA

u ab v bbbaaa w abba 17

Operasi String w a1a2 an v b1b2 bm

abba bbbaaa

Concatenation (Penyambungan)

wv a1a2  anb1b2 bm TEORI BAHASA OTOMATA

abbabbbaaa 18

w a1a2 an

ababaaabbb

Reverse (Pembalikan)

w an a2a1 R


bbbaaababa 19

Panjang String w a1a2 an • Panjang :

w n

• Contoh :

abba 4 aa 2


a 1

20

Panjang Concatenation uv u v • Contoh :

u aab, u 3 v abaab, v 5 uv aababaab 8 uv u v 3 5 8


21

String Kosong • string tanpa huruf:

• Observasi:



0 w ww


abba abbaabba

22

Substring • Substring dari string: subsequen dari karakter yg berurutan String

Substring

abbab

ab

abbab

abba

abbab

b

abbab

bbab


23

Prefix and Suffix abbab

Prefixes

 a ab abb abba abbab TEORI BAHASA OTOMATA

Suffixes

abbab bbab bab

w uv prefix suffix

ab b

 24

Operasi Lain

 abba abbaabba 2

• Contoh:

• Definisi: –

w  0  abba 


0

25

Operasi * •

* : Himpunan seluruh string yg mungkin dari alphabet 

 a,,bb *  , a, b, aa, ab, ba, bb, aaa, aab,


26

Operasi +

: Himpunan seluruh string yg mungking  dari alphabet kecuali 

 a, b *  , a, b, aa, ab, ba, bb, aaa, aab, 

 *  

  a, b, aa, ab, ba, bb, aaa, aab, TEORI BAHASA OTOMATA

27

Bahasa • Bahasa adalah subset dari • Contoh:

*

 a,b *  , a, b, aa, ab, ba, bb, aaa,

• Bahasa:

   a , aa , aab  { , abba , baba , aa , ab , aaaaaa }


28

Catatan: Himpunan

 { } {}

Ukuran Himpunan Ukuran Himpunan Panjang String TEORI BAHASA OTOMATA

{ }  0 {} 1

0 29

Contoh lain • Bahasa Tidak Terbatas

 ab aabb aaaaabbbbb TEORI BAHASA OTOMATA

L

L {a b : n 0} n n

abb L

30

Operasi dalam Bahasa • Menggunakan operasi himpunan

a, ab, aaaa bb, ab{a, ab, bb, aaaa} a, ab, aaaa bb, ab{ab} a, ab, aaaa bb, ab a, aaaa L * L a, ba, b, aa, ab, bb, aaa,

• Complement:


31

Reverse • Definisi:

L {w : w L}

• Contoh:

ab, aab,baba ba, baa, abab

R

R

R

L {a b : n 0} n n

L {b a : n 0} R


n n

32

Concatenation • definisi:

• contoh:

L1L2  xy : x L1, y L2 

a, ab, ba  b, aa  ab, aaa , abb, abaa , bab, baaa


33

Operasi Lain n L   LL  L • Definisi: n

 a, b a, b a, b  a, b  aaa, aab, aba, abb, baa, bab, bba, bbb 3

• Special kasus:


L 0   0  a , bba , aaa   

34

Contoh L {a b : n 0} n n

L {a b a b : n, m 0} 2

n n m m

2

aabbaaabbbL TEORI BAHASA OTOMATA

35

Star-Closure (Kleene *) • Definisi:

L* L L L 

• Contoh:


0

1

2

,     a,bb,   a,bb*   aa , abb , bba , bbbb ,    aaa,aabb,abba, abbbb,   36

Positive Closure • Definition:



L L L  L *    1

2

a, bb,      a, bb aa, abb, bba, bbbb,  aaa, aabb, abba, abbbb,   TEORI BAHASA OTOMATA

37

Pustaka 1. 2. 3. 4. 5. 6.

Tedy Setiadi, Diktat Teori Bahasa dan Otomata, Teknik Informatika UAD, 2005 Hopcroft John E., Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 2rd, Addison-Wesley,2000 Martin C. John, Introduction to Languages and Theory of Computation, McGraw-Hill Internatioanal edition,1991 Linz Peter,Introduction to Formal Languages & Automata, DC Heath and Company, 1990 Dulimarta Hans, Sudiana, Catatan Kuliah Matematika Informatika, Magister Teknik Informatika ITB, 1998 Hinrich Schütze, IMS, Uni Stuttgart, WS 2006/07, Slides based on RPI CSCI 2400


38

Pengantar TBO. Pertemuan Ke-2. Sri Handayaningsih, S.T., M.T. Teknik Informatika

Recommend Documents