Pengantar TBO

1

Sri Handayaningsih, S.T., M.T.Email : ning_s12@yahoo.com

Teknik Informatika

Pertemuan Ke-2

TIU dan TIK

Mengenal konsep bahasa dan otomataserta berbagai penerapannya, antara lain:

a. Simbol, alfabetb. String dan operasi yang adac. Bahasa dan Operasi yang ada

TEORI BAHASA OTOMATA2

c. Bahasa dan Operasi yang adad. star closure dan positif closuree. Bentuk Otomataf. Contoh Aplikasi

Computasi

CPU memory

TEORI BAHASA OTOMATA3

CPU memory

CPU

input memory

temporary memory

TEORI BAHASA OTOMATA4

CPU

output memory

Program memory

CPU

input memory

temporary memory

3)( xxf Contoh:

TEORI BAHASA OTOMATA5

CPU

output memoryProgram memory

Compute 1 xx

Compute 2 xx 2

CPU

input memorytemporary memory

3)( xxf

2x

TEORI BAHASA OTOMATA6

CPU

output memoryProgram memory

compute xx

compute xx 2

CPU

input memory

temporary memory 3)( xxf

2x

42*2 z82*)( zxf

TEORI BAHASA OTOMATA7

CPU

output memoryProgram memory

compute xx

compute xx 2

CPU

input memory

temporary memory 3)( xxf

2x

42*2 z82*)( zxf

TEORI BAHASA OTOMATA8

CPU

output memoryProgram memory

compute xx

compute xx 2

8)( xf

Automaton

CPU

input memory

temporary memory

Automaton

TEORI BAHASA OTOMATA9

CPU

output memory

Program memory

Perbedaan dari beberapa OtomataPerbedaan berdasarkan temporary memory

• Finite Automata: Tidak mempunyai

• Pushdown Automata: Bentuknya Stack

TEORI BAHASA OTOMATA10

• Turing Machines: Pengaccessan memory

secara random

input memory

temporary memory

Finite

Finite Automaton (FA)

TEORI BAHASA OTOMATA11

output memory

Finite

Automaton

Contoh: Mesin Pencari Kata

(Kekuatan komputasi kecil)

input memory

Stack

Pushdown

Pushdown Automaton (PDA)

Push, Pop

TEORI BAHASA OTOMATA12

input memory

output memory

Pushdown

Automaton

Contoh : Compilers pada bahasa pemrograman

(Kekuatan komputasi medium)

input memory

Random Access Memory

Turing

Mesin Turing

TEORI BAHASA OTOMATA13

input memory

output memory

Turing

Machine

Contoh : Banyak Algoritma

(Kekuatan komputasi Tinggi)

Finite

AutomataPushdown

AutomataMesin

Turing

Power of AutomataDalam Menyelesaikan Permasalahan

TEORI BAHASA OTOMATA14

Turing

Kekuatan rendah Kekuatan tinggi

Bahasa

TEORI BAHASAOTOMATA

15

• Bahasa adalah kumpulan dari string

• String : Kumpulan dari huruf

TEORI BAHASA OTOMATA16

– contoh: “cat”, “dog”, “house”, …

– terdefinisi pada alphabet: zcba ,,,,

Alphabets and Strings• Alphabet menggunakan huruf kecil:

• String ba,

a

TEORI BAHASA OTOMATA17

abbawbbbaaavabu

baaabbbaabababaabbaaba

Operasi String

m

n

bbbv

aaaw

21

21

bbbaaaabba

TEORI BAHASA OTOMATA18

mn bbbaaawv 2121

Concatenation (Penyambungan)

abbabbbaaa

naaaw 21 ababaaabbb

TEORI BAHASA OTOMATA19

12aaaw nR

Reverse (Pembalikan)

bbbaaababa

Panjang String

• Panjang :

naaaw 21

nw

TEORI BAHASA OTOMATA20

• Contoh :

1

2

4

a

aa

abba

Panjang Concatenation

• Contoh :

vuuv

3, uaabu

TEORI BAHASA OTOMATA21

853

8

5,

vuuv

aababaabuv

vabaabv

String Kosong• string tanpa huruf:

• Observasi:

0

TEORI BAHASA OTOMATA22

• Observasi:

abbaabbaabba

www

0

Substring• Substring dari string:

subsequen dari karakter yg berurutan

String Substring

TEORI BAHASA OTOMATA23

String Substring

bbabbabbaab

abbababbababbababbab

Prefix and Suffix

Prefixes Suffixes

abbab

a

bbababbab

uvw

prefix

TEORI BAHASA OTOMATA24

abbababbaabbaba

babbabbbab prefix

suffix

Operasi Lain

• Contoh: abbaabbaabba 2

TEORI BAHASA OTOMATA25

• Definisi:– 0w

0abba

Operasi *• : Himpunan seluruh string yg mungkin

dari alphabet*

,ba

TEORI BAHASA OTOMATA26

,,,,,,,,,*,

aabaaabbbaabaababa

Operasi +: Himpunan seluruh string yg mungking

dari alphabet kecuali

,,,,,,,,,*,

aabaaabbbaabaababa

TEORI BAHASA OTOMATA27

,,,,,,,,,* aabaaabbbaabaaba

*

,,,,,,,, aabaaabbbaabaaba

Bahasa

• Bahasa adalah subset dari

• Contoh:

*

,ba

TEORI BAHASA OTOMATA28

• Bahasa:

,,,,,,,,* aaabbbaabaaba

},,,,,{,,

aaaaaaabaababaabbaaabaaa

Catatan:

}{}{

0}{

Himpunan

Ukuran Himpunan

TEORI BAHASA OTOMATA29

0}{

1}{

0

Ukuran Himpunan

Ukuran Himpunan

Panjang String

Contoh lain

• Bahasa Tidak Terbatas }0:{ nbaL nn

TEORI BAHASA OTOMATA30

aaaaabbbbbaabbab

L Labb

Operasi dalam Bahasa• Menggunakan operasi himpunan aaaaaabbbaaaaaba

ababbbaaaaabaaaaabbabaabbbaaaaaba

,,,,}{,,,

},,,{,,,

TEORI BAHASA OTOMATA31

• Complement:

aaaaaabbbaaaaaba ,,,,

LL * ,,,,,,, aaabbabaabbaa

Reverse

• Definisi:

• Contoh:

}:{ LwwL RR

ababbaabababaaabab R ,,,,

TEORI BAHASA OTOMATA32

• Contoh: ababbaabababaaabab ,,,,

}0:{

}0:{

nabL

nbaL

nnR

nn

Concatenation

• definisi: 2121 ,: LyLxxyLL

TEORI BAHASA OTOMATA33

• contoh:

baaabababaaabbaaaab

aabbaaba

,,,,,

,,,

Operasi Lain• Definisi:

n

n LLLL

bbbbbababbaaabbabaaabaaa

babababa,,,,,,,

,,,, 3

TEORI BAHASA OTOMATA34

• Special kasus:

bbbbbababbaaabbabaaabaaa ,,,,,,,

0

0

,, aaabbaa

L

Contoh

}0:{ nbaL nn

}0,:{2 mnbabaL mmnn

TEORI BAHASA OTOMATA35

}0,:{2 mnbabaL mmnn

2Laabbaaabbb

Star-Closure (Kleene *)

• Definisi: 210* LLLL

TEORI BAHASA OTOMATA36

• Contoh:

,,,,,,,,

,,,

*,

abbbbabbaaabbaaabbbbbbaabbaa

bbabba

Positive Closure

• Definition:

*

21

LLLL

TEORI BAHASA OTOMATA37

,,,,,,,,

,,,

abbbbabbaaabbaaabbbbbbaabbaa

bbabba

Pustaka1. Tedy Setiadi, Diktat Teori Bahasa dan Otomata,

Teknik Informatika UAD, 20052. Hopcroft John E., Rajeev Motwani, Jeffrey D. Ullman,

Introduction to Automata Theory, Languages, andComputation, 2rd, Addison-Wesley,2000

3. Martin C. John, Introduction to Languages and Theory ofComputation, McGraw-Hill Internatioanal edition,1991

TEORI BAHASA OTOMATA38

3. Martin C. John, Introduction to Languages and Theory ofComputation, McGraw-Hill Internatioanal edition,1991

4. Linz Peter,Introduction to Formal Languages & Automata,DC Heath and Company, 1990

5. Dulimarta Hans, Sudiana, Catatan Kuliah MatematikaInformatika, Magister Teknik Informatika ITB, 1998

6. Hinrich Schütze, IMS, Uni Stuttgart, WS 2006/07,Slides based on RPI CSCI 2400