pertemuan 2-pengenalan tbo [compatibility mo. bahasa dan operasi yang ada teori bahasaotomata 2 ......

Pengantar TBO

1

Sri Handayaningsih, S.T., M.T.Email : [email protected]

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


CPU memory

CPU

input memory

temporary memory


CPU

output memory

Program memory

CPU

input memory

temporary memory

3)( xxf Contoh:


CPU

output memoryProgram memory

Compute 1 xx

Compute 2 xx 2

CPU

input memorytemporary memory

3)( xxf

2x


CPU


compute xx

compute xx 2

CPU

input memory

temporary memory 3)( xxf

2x

42*2 z82*)( zxf


CPU


compute xx

compute xx 2

CPU

input memory

temporary memory 3)( xxf

2x

42*2 z82*)( zxf


CPU


compute xx

compute xx 2

8)( xf

Automaton

CPU

input memory

temporary memory

Automaton


CPU

output memory

Program memory

Perbedaan dari beberapa OtomataPerbedaan berdasarkan temporary memory

• Finite Automata: Tidak mempunyai

• Pushdown Automata: Bentuknya Stack


• Turing Machines: Pengaccessan memory

secara random

input memory

temporary memory

Finite

Finite Automaton (FA)


output memory

Finite

Automaton

Contoh: Mesin Pencari Kata

(Kekuatan komputasi kecil)

input memory

Stack

Pushdown

Pushdown Automaton (PDA)

Push, Pop


input memory

output memory

Pushdown

Automaton

Contoh : Compilers pada bahasa pemrograman

(Kekuatan komputasi medium)

input memory

Random Access Memory

Turing

Mesin Turing


input memory

output memory

Turing

Machine

Contoh : Banyak Algoritma

(Kekuatan komputasi Tinggi)

Finite

AutomataPushdown

AutomataMesin

Turing

Power of AutomataDalam Menyelesaikan Permasalahan


Turing

Kekuatan rendah Kekuatan tinggi

Bahasa

TEORI BAHASAOTOMATA

15

• Bahasa adalah kumpulan dari string

• String : Kumpulan dari huruf


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

– terdefinisi pada alphabet: zcba ,,,,

Alphabets and Strings• Alphabet menggunakan huruf kecil:

• String ba,

a


abbawbbbaaavabu

baaabbbaabababaabbaaba

Operasi String

m

n

bbbv

aaaw

21

21

bbbaaaabba


mn bbbaaawv 2121

Concatenation (Penyambungan)

abbabbbaaa

naaaw 21 ababaaabbb


12aaaw nR

Reverse (Pembalikan)

bbbaaababa

Panjang String

• Panjang :

naaaw 21

nw


• Contoh :

1

2

4

a

aa

abba

Panjang Concatenation

• Contoh :

vuuv

3, uaabu


853

8

5,

vuuv

aababaabuv

vabaabv

String Kosong• string tanpa huruf:

• Observasi:

0


• Observasi:

abbaabbaabba

www

0

Substring• Substring dari string:

subsequen dari karakter yg berurutan

String Substring


String Substring

bbabbabbaab

abbababbababbababbab

Prefix and Suffix

Prefixes Suffixes

abbab

a

bbababbab

uvw

prefix


abbababbaabbaba

babbabbbab prefix

suffix

Operasi Lain

• Contoh: abbaabbaabba 2


• Definisi:– 0w

0abba

Operasi *• : Himpunan seluruh string yg mungkin

dari alphabet*

,ba


,,,,,,,,,*,

aabaaabbbaabaababa

Operasi +: Himpunan seluruh string yg mungking

dari alphabet kecuali

,,,,,,,,,*,

aabaaabbbaabaababa


,,,,,,,,,* aabaaabbbaabaaba

*

,,,,,,,, aabaaabbbaabaaba

Bahasa

• Bahasa adalah subset dari

• Contoh:

*

,ba


• Bahasa:

,,,,,,,,* aaabbbaabaaba

},,,,,{,,

aaaaaaabaababaabbaaabaaa

Catatan:

}{}{

0}{

Himpunan

Ukuran Himpunan


0}{

1}{

0

Ukuran Himpunan

Ukuran Himpunan

Panjang String

Contoh lain

• Bahasa Tidak Terbatas }0:{ nbaL nn


aaaaabbbbbaabbab

L Labb

Operasi dalam Bahasa• Menggunakan operasi himpunan aaaaaabbbaaaaaba

ababbbaaaaabaaaaabbabaabbbaaaaaba

,,,,}{,,,

},,,{,,,


• Complement:

aaaaaabbbaaaaaba ,,,,

LL * ,,,,,,, aaabbabaabbaa

Reverse

• Definisi:

• Contoh:

}:{ LwwL RR

ababbaabababaaabab R ,,,,


• Contoh: ababbaabababaaabab ,,,,

}0:{

}0:{

nabL

nbaL

nnR

nn

Concatenation

• definisi: 2121 ,: LyLxxyLL


• contoh:

baaabababaaabbaaaab

aabbaaba

,,,,,

,,,

Operasi Lain• Definisi:

n

n LLLL

bbbbbababbaaabbabaaabaaa

babababa,,,,,,,

,,,, 3


• Special kasus:

bbbbbababbaaabbabaaabaaa ,,,,,,,

0

0

,, aaabbaa

L

Contoh

}0:{ nbaL nn

}0,:{2 mnbabaL mmnn


}0,:{2 mnbabaL mmnn

2Laabbaaabbb

Star-Closure (Kleene *)

• Definisi: 210* LLLL


• Contoh:

,,,,,,,,

,,,

*,

abbbbabbaaabbaaabbbbbbaabbaa

bbabba

Positive Closure

• Definition:

*

21

LLLL


,,,,,,,,

,,,

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


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

pertemuan 2-pengenalan tbo [compatibility mo. bahasa dan operasi yang ada teori bahasaotomata 2 ......

Documents