Teori Himpunan • Himpunan adalah sekumpulan entitas
Matematika Dasar untuk Teori Bahasa Otomata
• Notasi keanggotaan – x S –xS
Teori Bahasa & Otomata
• Menspesifikasikan himpunan
Semester Ganjil 2009/2010
• S = {0, 2, 4, 6,…} • S = {x: x 0, x genap} TEORI BAHASA & OTOMATA
TEORI BAHASA & OTOMATA
Shofwatul ‘Uyun, M.Kom
Shofwatul ‘Uyun, M.Kom
Operasi pada Himpunan • • • •
– tidak memiliki struktur – sifatnya hanya keanggotaan
Union () Intersection () Difference (-) Complementation (S )
Himpunan Tanpa Elemen • disebut Himpunan Kosong • Notasi: • Apakah hal berikut membingungkan? S = S - = S S = =U S=S
– S = { x : x U, x S }
TEORI BAHASA & OTOMATA
TEORI BAHASA & OTOMATA
Shofwatul ‘Uyun, M.Kom
Shofwatul ‘Uyun, M.Kom
Notasi • • • •
Himpunan Kosong () Subset () & proper subset () Disjoint S1 S2 = Himpunan finit(hingga) dan infinit(tak hingga) • |S| ukuran himpunan finit – Jumlah elemen himpunan S
Powerset & Cartesian Product • Powerset 2s – himpunan seluruh himpunan bagian dari S – S ={a,b,c}, 2S={,(a),(b),(c),(a,b),(a,c),(b,c),(a,b,c)}
• Cartesian Product – S = S1 S2 = {(x, y): x S1, y S2 } – S1={2, 4}, S2={1, 2} – S1 S2 = {(2, 1), (2, 2), (4, 1), (4, 2)},
TEORI BAHASA & OTOMATA
TEORI BAHASA & OTOMATA
Shofwatul ‘Uyun, M.Kom
Shofwatul ‘Uyun, M.Kom
1
Definisi Fungsi • Fungsi ( f )= suatu aturan yang memetakan elemen-elemen suatu himpunan (domain) ke elemen himpunan lain (range) f :S1 S2 • Fungsi total & fungsi parsial – total jika domain adalah seluruh anggota S1
perbedaan
Fungsi & Relasi
• Fungsi – Pasangan elemen: {(x1, y1), (x2, y2), (x3, y3),…} – xi paling banyak muncul sekali sebagai elemen pertama pada pasangan elemen
• Relasi – Bentuk umum dari fungsi – Suatu elemen dapat dipetakan ke lebih dari satu elemen range
TEORI BAHASA & OTOMATA
TEORI BAHASA & OTOMATA
Shofwatul ‘Uyun, M.Kom
Shofwatul ‘Uyun, M.Kom
Ekuivalensi • Salah satu macam relasi • Ekuivalensi x y
definisi
Graph
• Graph = suatu bentuk yang terdiri atas dua himpunan hingga (finite set), yaitu himpunan vertek dan himpunan edge(tepi)
– Reflexivity
– Vertek, V = { v1, v2, v3, …} – Edge, E = { e1, e2, e3, …} – Setiap edge adalah pasangan dari vertek ei =(vj, vk )
• x x untuk semua x
– Symmetry • Jika x y maka y x
– Transitivity • Jika x y dan y z maka x z TEORI BAHASA & OTOMATA
TEORI BAHASA & OTOMATA
Shofwatul ‘Uyun, M.Kom
Shofwatul ‘Uyun, M.Kom
visualisasi
Graph
visualisasi
Graph
• Visualisasi Graph – Vertek dan edge biasanya diberi label – Vertek lingkaran – Edge garis dengan tanda panah di salah satu ujungnya
v1
v2
v3
– V = { v1, v2, v3 } – E = {(v1, v3 ), (v3, v1 ), (v3, v2 ), (v3, v3 )}
• walk, path, simple path, cycle, simple cycle TEORI BAHASA & OTOMATA
TEORI BAHASA & OTOMATA
Shofwatul ‘Uyun, M.Kom
Shofwatul ‘Uyun, M.Kom
2
definisi
Tree
visualisasi
Tree
• Tree = suatu tipe khusus dari graph – Directed graph yang tidak memiliki cycles dan memiliki suatu vertek khusus disebut root – Hanya terdapat satu path dari root ke setiap vertek lain – Root = vertek tanpa edge yang menuju kepadanya – Daun = vertek tanpa edge yg keluar darinya
root
Level 0
daun
kedalaman = 3
Level 3
TEORI BAHASA & OTOMATA Shofwatul ‘Uyun, M.Kom
Teknik
Pembuktian
induktif & kontradiktif • Induktif – diasumsikan benar untuk: P1, P2, … , Pn (disebut asumsi induktif)
– diperlihatkan benar untuk nilai awal-nya (basis)
– dibuktikan asumsi tsb juga benar untuk Pn+1
TEORI BAHASA & OTOMATA Shofwatul ‘Uyun, M.Kom
Contoh Teknik Pembuktian induktif
• Buktikan bahwa sebuah binary tree (pohon biner) dengan ketinggian n memiliki paling banyak 2n daun!
• Pembuktian: dinotasikan banyaknya daun adalah l(n), shg l(n) 2n Basis: l(0) = 1 = 20 (yaitu root) Asumsi Induktif: l(i) 2i , untuk i = 0, 1, 2, …, n Langkah induktif: l(n+1) = 2 l(n)
(disebut langkah induktif) l(n+1) 2 x 2n = 2n+1
• Kontradiktif – melakukan asumsi sebaliknyaTEORI BAHASA & OTOMATA Shofwatul ‘Uyun, M.Kom
Contoh Teknik
Pembuktian
TEORI BAHASA & OTOMATA Shofwatul ‘Uyun, M.Kom
kontradiktif
• Buktikan bahwa 2 bukan bilangan rasional!
• Pembuktian: Diasumsikan sebaliknya, yaitu 2 adalah bilangan rasional, sehingga dapat ditulis sbb: n 2 = m 2 m2 = n2
Tiga Konsep Dasar Bahasa, Grammar, & Otomata
terlihat bahwa n2 genap, sehingga n = 2k 2 m2 = 4k2
m2 = 2k2
Karena m adalah genap maka hal ini kontradiksi dengan asumsi kita, sehingga m dan n tidak ada dan 2 bukan TEORI BAHASA & OTOMATA Shofwatul ‘Uyun, M.Kom bilangan rasional
TEORI BAHASA & OTOMATA Shofwatul ‘Uyun, M.Kom
3
Bahasa • Bahasa Alami: bahasa inggris, indonesia, belanda, … • Definisi informal: sebuah sistem yang sesuai untuk mengekspresikan suatu ide, fakta, atau konsep, termasuk didalamnya sekumpulan simbol dan aturan-aturan untuk memanipulasinya
Bahasa Formal • Alfabet (Σ) – himpunan simbol, non-empty set
• String : rangkaian hingga simbol pada alfabet • Contoh: Σ = {a, b}, abab dan aaabbb adalah string pada Σ
• Bahasa formal ?
TEORI BAHASA & OTOMATA
TEORI BAHASA & OTOMATA
Shofwatul ‘Uyun, M.Kom
Shofwatul ‘Uyun, M.Kom
Bahasa Formal • Operasi pada string
Definisi
Bahasa Formal
• Sebuah bahasa didefiniskan secara umum sebagai subset dari Σ*
– Concatenation – Reverse – Panjang string
• = empty string • Σ* = konkatenasi simbol pada Σ sebanyak 0 atau lebih kali (disebut star closure of Σ) • Σ+ = Σ*-(} (disebut positif closure of Σ)
– Suatu string w pada suatu bahasa L disebut kata atau kalimat pada L – Pada teori bahasa formal kata dan kalimat tidak dibedakan
• L* = L0 L1 L2 … • L+ = L1 L2 …
TEORI BAHASA & OTOMATA
TEORI BAHASA & OTOMATA
Shofwatul ‘Uyun, M.Kom
Shofwatul ‘Uyun, M.Kom
Grammar • Grammar (pada bahasa alami) Untuk menentukan apakah suatu kalimat memiliki format yang baku atau tidak – Pada bahasa inggris “Sebuah kalimat dapat terdiri dari sebuah noun phrase diikuti oleh sebuah predicate“ – <sentence> <noun_phrase><predicate> <noun_phrase> <article><noun> <predicate>
Contoh
Grammar
• Misal : – <article> = “a” dan “the” – <noun> = “boy” dan “dog” – = “runs” dan “walks”
• Contoh kalimat: “a boy runs”, “the dog walks”
TEORI BAHASA & OTOMATA
TEORI BAHASA & OTOMATA
Shofwatul ‘Uyun, M.Kom
Shofwatul ‘Uyun, M.Kom
4
Grammar Formal • Sebuah grammar didefinisikan sebagai sebuah quadruple G = (V, T, S, P)
• Production rule adalah inti dari grammar menspesifikasikan bagaimana suatu grammar mengubah suatu string manjadi string yang lain, dan mendefinisikan bahasa sesuai dengan grammar yang dipakai
• Format: x y
dimana: V = himpunan hingga objek yang disebut variabel T = himpunan hingga objek yang disebut terminal symbol S V = spesial symbol yang dinamakan start variabel P = sebuah himpunan berhingga dari production
…
dimana x (V T )+ dan y (V T )*
• Misal : – – – –
Sebuah string w memiliki format : w uxv Production x y applicable (dapat diaplikasikan) untuk string w String baru : z uyv Dituliskan: w z
TEORI BAHASA & OTOMATA
TEORI BAHASA & OTOMATA
Shofwatul ‘Uyun, M.Kom
Shofwatul ‘Uyun, M.Kom
Production Rule • Jika: w1 w2
Production Rule
wn
Bahasa didefinisikan oleh Grammar • Jika G = (V, T, S, P) adalah sebuah grammar. Maka himpunan:
dikatakan w1 menurunkan wn
• w1 wn *
* (tanda bintang) mengindikasikan jumlah langkah yang tak tentu (termasuk nol) untuk menurunkan wn dari w1
+ • w1 wn +
(tanda plus) mengindikasikan minimal terdapat satu produksi untuk menurunkan wn dari w1
L(G) = {wT*: S * w}
adalah bahasa yang dihasilkan oleh G. • Jika w L(G), maka deretan S w1 w2 … wn w adalah penurunan untuk kalimat/kata w • String: S, w1, w2, …,wn disebut sentential forms
TEORI BAHASA & OTOMATA
TEORI BAHASA & OTOMATA
Shofwatul ‘Uyun, M.Kom
Shofwatul ‘Uyun, M.Kom
Contoh • Diberikan grammar G = ({S},{a,b}, S, P), dengan P sbb.: S aSb S Maka : S aSb aaSbb aabb dapat dituliskan : S * aabb • Maka bahasa yang dihasilkan oleh G adalah : L(G) = {an bn : n 0}
Latihan 1. Cari grammar yang menghasilkan bahasa L(G) = {an bn+1 : n 0} ! 2. Definsikan bahasa yang dihasilkan oleh grammar dengan production berikut: S aA A bS S
TEORI BAHASA & OTOMATA
TEORI BAHASA & OTOMATA
Shofwatul ‘Uyun, M.Kom
Shofwatul ‘Uyun, M.Kom
5
Otomata • Model abstrak dari sebuah komputer digital • Fitur utama:
Model Visual
Otomata
Input File
– Membaca input berupa string simbol • Dari kiri ke kanan • Satu simbol pada satu waktu • Mendeteksi akhir string input
– Menghasilkan output – Memiliki control unit
Control Unit
Storage
• Mengontrol perpindahan state
– Dapat memiliki alat penyimpan sementara TEORI BAHASA & OTOMATA Shofwatul ‘Uyun, M.Kom
Tipe
Output
TEORI BAHASA & OTOMATA Shofwatul ‘Uyun, M.Kom
Otomata
• Deterministic Finit Otomata (DFA) – jika diketahui konfigurasi dari input, internal state, dan isi penyimpan sementara maka bisa diprediksi kelakuan otomata kemudian
• Non-deterministic Finit Otomata (NFA) – terdapat beberapa kemungkinan perpindahan dari suatu state
• Accepter : output “ya/diterima” atau “tidak/ditolak” • Transducer : output berupa string TEORI BAHASA & OTOMATA
TEORI BAHASA & OTOMATA
Shofwatul ‘Uyun, M.Kom
Shofwatul ‘Uyun, M.Kom
6