PERTEMUAN I PDF

Preview

Summary

PERTEMUAN I PENDAHULUAN Teori Bahasa Teori bahasa membicarakan bahasa formal (formal language), terutama untuk kepentingan perancangan kompilator (compiler) dan pemroses naskah (text processor). Bahasa formal adalah kumpulan kalimat. Semua kalimat dalam sebuah bahasa dibangkitkan oleh sebuah tata ba...

Description

PERTEMUAN I

PENDAHULUAN Teori Bahasa Teori bahasa membicarakan bahasa formal (formal language), terutama untuk kepentingan perancangan kompilator (compiler) dan pemroses naskah (text processor). Bahasa formal adalah kumpulan kalimat. Semua kalimat dalam sebuah bahasa dibangkitkan oleh sebuah tata bahasa (grammar) yang sama. Sebuah bahasa formal bisa dibangkitkan oleh dua atau lebih tata bahasa berbeda. Dikatakan bahasa formal karena grammar diciptakan mendahului pembangkitan setiap kalimatnya. Bahasa manusia bersifat sebaliknya; grammar diciptakan untuk meresmikan kata-kata yang hidup di masyarakat. Dalam pembicaraan selanjutnya ‘bahasa formal’ akan disebut ‘bahasa’ saja.

Automata Automata adalah mesin abstrak yang dapat mengenali (recognize), menerima (accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu. Untuk memodelkan hardware dari komputer diperkenalkan otomata. Otomata adalah fungsi-fungsi dari komputer digital. Menerima input, menghasilkan output, bisa memiliki penyimpanan sementara dan mampu membuat keputusan dalam mentransformasikan input ke output. Sebuah bahasa formal adalah suatu abstraksi terdiri dari himpunan simbol-simbol dan aturan-aturan yang mana simbol-simbol tersebut bisa dikombinasikan ke dalam entitas yang disebut kalimat. Meskipun bahasa formal yang dipelajari di sini lebih sederhana daripada bahasa pemrograman, mereka mempunyai banyak hal yan g penting. Kita bisa mempelajari banyak tentang bahasa pemrograman dari bahasa formal.

Otomata merupakan suatu sistem yang terdiri atas sejumlah berhingga state, dimana state menyatakan informasi mengenai input yang lalu dan dapat dianggap sebagai memori mesin. Input pada mesin otomata dianggap sebagai bahasa yang harus dikenali oleh mesin. Selanjutnya, mesin otomata membuat keputusan yang mengindikasikan apakah input itu diterima atau tidak.

Beberapa Pengertian Dasar • Simbol adalah sebuah entitas abstrak (seperti halnya pengertian titik dalam geometri). Sebuah huruf atau sebuah angka adalah contoh simbol. • String adalah deretan terbatas (finite) simbol-simbol. Sebagai contoh, jika a, b, dan c adalah tiga buah simbol maka abcb adalah sebuah string yang dibangun dari ketiga simbol tersebut. • Jika w adalah sebuah string maka panjang string dinyatakan sebagai | w | dan didefinisikan sebagai cacahan (banyaknya) simbol yang menyusun string tersebut. Sebagai contoh, jika w = abcb maka | w | = 4. • String hampa adalah sebuah string dengan nol buah simbol. String hampa dinyatakan dengan simbol ε (atau ^) sehingga |ε |= 0. String hampa dapat dipandang sebagai simbol hampa karena keduanya tersusun dari nol buah simbol. • Alfabet adalah hinpunan hingga (finite set) simbol-simbol

Operasi Dasar String Diberikan dua string : x = abc, dan y = 123 • Prefik string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol paling belakang dari string w tersebut. Contoh : abc, ab, a, dan ε adalah semua Prefix(x) • ProperPrefix string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol paling belakang dari string w tersebut. Contoh : ab, a, dan ε adalah semua ProperPrefix(x) • Postfix (atau Sufix) string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol paling depan dari string w tersebut. Contoh : abc, bc, c, dan ε adalah semua Postfix(x)

• ProperPostfix (atau PoperSufix) string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol paling depan dari string w tersebut. Contoh : bc, c, dan ε adalah semua ProperPostfix(x) • Head string w adalah simbol paling depan dari string w. Contoh : a adalah Head(x) • Tail string w adalah string yang dihasilkan dari string w dengan menghilangkan simbol paling depan dari string w tersebut. Contoh : bc adalah Tail(x) • Substring string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol paling depan dan/atau simbolsimbol paling belakang dari string w tersebut. Contoh : abc, ab, bc, a, b, c, dan ε adalah semua Substring(x) • ProperSubstring string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol paling depan dan/atau simbolsimbol paling belakang dari string w tersebut. Contoh : ab, bc, a, b, c, dan ε adalah semua Substring(x)

• Subsequence string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol dari string w tersebut. Contoh : abc, ab, bc, ac, a, b, c, dan ε adalah semua Subsequence(x) • ProperSubsequence string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol dari string w tersebut. Contoh : ab, bc, ac, a, b, c, dan ε adalah semua Subsequence(x) • Concatenation adalah penyambungan dua buah string. Operator concatenation adalah concate atau tanpa lambang apapun. Contoh : concate(xy) = xy = abc123 • Alternation adalah pilihan satu di antara dua buah string. Operator alternation adalah alternate atau |. Contoh : alternate(x|y) = x | y = abc atau 123 • Kleene Closure : x* = ε | x | xx  xxx |… = ε | x | x 2 | x 3 |… • Positive Closure : x + = x | xx | xxx |… = x |x 2 | x 3 |…

Konsep Dasar 1. Dalam pembicaraan grammar, anggota alfabet dinamakan simbol terminal atau token. 2. Kalimat adalah deretan hingga simbol-simbol terminal. 3. Bahasa adalah himpunan kalimat-kalimat. Anggota bahasa bisa tak hingga kalimat. 4. Simbol-simbol berikut adalah simbol terminal (VT) : • huruf kecil alfabet, misalnya : a, b, c • simbol operator, misalnya : +, −, dan × • simbol tanda baca, misalnya : (, ), dan ; • string yang tercetak tebal, misalnya : if, then, dan else. 5. Simbol-simbol berikut adalah simbol non terminal (VN) : • huruf besar alfabet, misalnya : A, B, C • huruf S sebagai simbol awal • string yang tercetak miring, misalnya : expr dan stmt. 6. Huruf besar akhir alfabet melambangkan simbol terminal atau non terminal, misalnya : X, Y, Z. 7. Huruf kecil akhir alfabet melambangkan string yang tersusun atas simbol-simbol terminal, misalnya : x, y, z.

8. Huruf yunani melambangkan string yang tersusun atas simbol-simbol terminal atau simbol-simbol non terminal atau campuran keduanya, misalnya : α, β, dan γ. 9. Sebuah produksi dilambangkan sebagai α → β, artinya : dalam sebuah derivasi dapat dilakukan penggantian simbol α dengan simbol β. 10. Simbol α dalam produksi berbentuk α → β disebut ruas kiri produksi sedangkan simbol β disebut ruas kanan produksi. 11. Derivasi adalah proses pembentukan sebuah kalimat atau sentensial. Sebuah derivasi dilambangkan sebagai : α ⇒ β. 12. Sentensial adalah string yang tersusun atas simbol-simbol terminal atau simbol-simbol non terminal atau campuran keduanya. 13. Kalimat adalah string yang tersusun atas simbol-simbol terminal. Jelaslah bahwa kalimat adalah kasus khusus dari sentensial. 14. Pengertian terminal berasal dari kata terminate (berakhir), maksudnya derivasi berakhir jika sentensial yang dihasilkan adalah sebuah kalimat (yang tersusun atas simbol-simbol terminal itu). 15. Pengertian non terminal berasal dari kata not terminate (belum/tidak berakhir), maksudnya derivasi belum/tidak berakhir jika sentensial yang dihasilkan mengandung simbol non terminal.

Grammar dan Klasifikasi Chomsky Grammar G didefinisikan sebagai pasangan 4 tuple : V T , V N , S, dan Q, dan dituliskan sebagai G(V T , V N , S, Q), dimana : VT : himpunan simbol-simbol terminal (atau himpunan token -token, atau alfabet) VN : himpunan simbol-simbol non terminal S ∈ V N : simbol awal (atau simbol start) Q : himpunan produksi

Berdasarkan komposisi bentuk ruas kiri dan ruas kanan produksinya (α → β), Noam Chomsky mengklasifikasikan 4 tipe grammar : 1. Grammar tipe ke-0 : Unrestricted Grammar (UG) Ciri : α, β ∈ (V T | VN )*, | α | > 0 2. Grammar tipe ke-1 : Context Sensitive Grammar (CSG) Ciri : α, β ∈ (V T | VN )*, 0 < | α | ≤ | β | 3. Grammar tipe ke-2 : Context Free Grammar (CFG) Ciri : α ∈ V N , β ∈ (V T | VN )* 4. Grammar tipe ke-3 : Regular Grammar (RG) Ciri : α ∈ V N , β ∈ {V T , V T VN } atau α ∈ V N , β ∈ {V T , V N VT } Mengingat ketentuan simbol-simbol (hal. 3 no. 4 dan 5), ciri-ciri RG sering dituliskan sebagai : α ∈ V N , β ∈ {a, bC} atau α ∈ V N , β ∈ {a, Bc}

Contoh Analisa Penentuan Type Grammar 1. Grammar G1 dengan Q1 = {S → aB, B → bB, B → b}. Ruas kiri semua produksinya terdiri dari sebuah V N maka G1 kemungkinan tipe CFG atau RG. Selanjutnya karena semua ruas kanannya terdiri dari sebuah V T atau string V T VN maka G1 adalah RG. 2. Grammar G 2 dengan Q 2 = {S → Ba, B → Bb, B → b}. Ruas kiri semua produksinya terdiri dari sebuah VN maka G 2 kemungkinan tipe CFG atau RG. Selanjutnya karena semua ruas kanannya terdiri dari sebuah V T atau string VN V T maka G 2 adalah RG. 3. Grammar G3 dengan Q 3 = {S → Ba, B → bB, B → b}. Ruas kiri semua produksinya terdiri dari sebuah VN maka G 3 kemungkinan tipe CFG atau RG. Selanjutnya karena ruas kanannya mengandung string V T VN (yaitu bB) dan juga string VN V T (Ba) maka G 3 bukan RG, dengan kata lain G 3 adalah CFG. 4. Grammar G 4 dengan Q 4 = {S → aAb, B → aB}. Ruas kiri semua produksinya terdiri dari sebuah VN maka G 4 kemungkinan tipe CFG atau RG. Selanjutnya karena ruas kanannya mengandung string yang panjangnya lebih dari 2 (yaitu aAb) maka G 4 bukan RG, dengan kata lain G 4 adalah CFG.

5. Grammar G5 dengan Q 5 = {S → aA, S → aB, aAb → aBCb}. Ruas kirinya mengandung string yang panjangnya lebih dari 1 (yaitu aAb) maka G5 kemungkinan tipe CSG atau UG. Selanjutnya karena semua ruas kirinya lebih pendek atau sama dengan ruas kananya maka G 5 adalah CSG. 6. Grammar G 6 dengan Q 6 = {aS → ab, SAc → bc}. Ruas kirinya mengandung string yang panjangnya lebih dari 1 maka G 6 kemungkinan tipe CSG atau UG. Selanjutnya karena terdapat ruas kirinya yang lebih panjang daripada ruas kananya (yaitu SAc) maka G 6 adalah UG.

Tipe 0 ⇒ Mesin Automata ⇒ Mesin Turing Tipe 1 ⇒ Mesin Automata ⇒ Linier bounded Tipe 2 ⇒ Mesin Automata ⇒ Push Down ( NFA [Non Deterministic Finite Automata] } Tipe 3 ⇒ DFA, NFA ( DFA [Deterministic Finite Automata] ) Alternate → | x|y=y|x | → pilihan x atau y Cleen closure ( * ) x* = ε x | xx | xxx |….. Positive closure ( + ) → tanpa hampa x + = x | xx | xxx |…….. ( x * )* = x * ( x | y )* = ε | x|y | xx | yy | xy | yx | xxy | yyx |… ( xy )* = xy | xyxy | xyxyxy |…..

Tipe 3 ?

BENAR ATAU SALAH jawaban dibawah ini

a. B → bdB

VN → VTVTVN ( Ya )

b. B → bcdef

VN → VTVTVTVTVT ( Tidak )

c. A → ass

VN → VTVNVN ( Tidak )

d. Ad → dB

VNVT → VTVN ( Tidak )

Tipe 2 ? e. B → bcdefG VN → VTVTVTVTVTVN ( Ya ) f. A → Ace

VN → VNVTVT ( Ya )

g. A → ab

VN → VTVT ( Ya )

h. A → aSa

VN → VTVNVT ( Ya )

Tipe 1 i.

Ad → b

j.

AB → cde VNVN→ VTVTVT ( Ya )

k.

Ad → dB

l.

VTVT → VT ( Tidak ) VNVT→VTVN ( Ya )

adC → DE VTVTVN → VNVN ( Tidak )

Tipe 0 m. AB → cde VNVN → VTVTVT ( Tidak ) n.

adC → DE VTVTVN → VNVN ( Ya )

o.

ad → b

VTVT → VN ( Ya )

PERTEMUAN 2 FINITE STATE AUTOMATA ( FSA )

FINITE STATE AUTOMATA ( FSA ) FSA merupakan mesin automata dari bahasa Regular. FSA memiliki state yang banyaknya berhingga dan dapat berpindah – pindah dari satu state ke state yang lain. Perpindahan state dinyatakan dengan transisi. FSA dapat menerima input & menghasilkan output. Contoh : mesin automata untuk pencek pariti ganjil EvenO

1

1

Odd Odd Odd

O o

• Lingkaran menyatakan state/ kedudukan • Lingkaran ganda menyatakan state akhir ( final state ) • Label pada lingkaran adalah nama state tersebut Busur menyatakan transisi / perpindahan state Label pada busur adalah simbol input Lingkaran didahului oleh sebuah busur tanpa label menyatakan state awal Simbol input { 0.1}

State awal Even State akhir Odd Bila mesin mendapat Input : l l 0 l, apakah diterima oleh mesin? Input akan diterima bila berakhir pada hait atau final state . Untuk state yang dilakukan Even l Odd l Even O Even l Odd Berakhir pada state Odd, maka Input ll0l diterima oleh mesin

Bila mendapat input l0l, apakah diterima oleh mesin ? Untuk state yang dilakukan Even l Odd 0 Odd l Even Berakhir pada Even, maka Input l0l ditolak oleh mesin

Secara formal Finite State Automata dinyatakan dengan 5 tuple atau m = { Q, Σ, δ, S, F } Definisinya : Q = Himpunan state atau kedudukan Σ = Himpunan simbol input / masukan / abjad / angka δ = Fungsi transisi S = State awal / kedudukan awal, S € Q F = Himpunan state akhir, F € Q DFA ( Deterministic Finite Automata ) FSA NFA ( Non Deterministic Finite Automata ) •

DFA ( Deterministic Finite Automata) 1. Mesin DFA b a a qo

b

q1

q2

b a

Q = {q0, q1, q2} Σ = {a, b } S = {q0} F = {q2} Fungsi Transisi

Tabel Transisi

δ ( q0, a ) = qo

δ

δ ( qo, b ) = q1

q0 q0 q1

δ ( q1, a ) = q1

q1 q1 q2

δ ( q1, b ) = q2

q2 q1 q2

δ ( q2, a ) = q1 δ ( q2, b ) = q2

a

b

Jika mesin DFA tersebut mendapat input “abb”, apakah diterima oleh mesin? δ (q0, abb ) = δ (q0, bb) = δ (q1,b) = q2 Berakhir pada final state maka input diterima oleh mesin “abb” berada di akhir L( m ) Jika mesin mendapat Input string “baba” apakah merupakan L ( m )? δ (q0, baba ) = δ (q1, aba) = δ (q1, ba) = δ (q2,a) = q1 q1 bukan final state, berakhir pada state q1, maka input untuk string “baba” ditolak / direject oleh mesin & bukan L( m ) 2. Mesin DFA a,b qo

q 1

b

a

Q = {q0, q1} Σ = {a,b} S = {q0} F = {q1} Fungsi Transisi

Tabel Transisi

δ ( q0, a ) = q1

δ

δ ( q0, b ) = q1

q0 q1 q1

δ ( q1, a ) = q1

q1 q1 q0

a

b

δ ( q1, b ) = q0 JIka mesin DFA tersebut mendapat Input “abbaba”, apakah diterima oleh mesin δ ( q0, abbaba ) = δ ( q1, bbaba ) = δ ( q0,baba ) = δ ( q1, aba ) = δ ( q1, ba ) = δ ( q0, a ) = q1 Berakhir pada final state maka input diterima oleh mesin “ abbaba “ berada diakhir L ( m )

* NFA (Non Deterministic Finite Automata) 1. Mesin NFA a qo

a q1

b

Fungsi Transisi

Q = { q0, q1 }

δ { q0, a } = q1

Σ = { a, b }

δ { q0, b } = φ

S = { q0 }

δ { q1, a } = q1

F = { q1 }

δ { q1, b } = q0

δ

a

b

q0 q1

φ

q1 q1

q0

Himpunan φ merupakan NFA Jika mendapat input “ aaabbbaaa “ δ ( q0, aaabbbaaa ) = δ ( q1, aabbbaaa ) = δ ( q1, abbbaaa ) = δ ( q1, bbbaaa ) = δ ( q0, bbaaa ) = δ ( φ ) “ ditolak / direject oleh mesin & bukan L ( m ) “

2. Mesin NFA b qo

a a b

a

q1

b q2

a Q = { q0, q1, q2 } Σ = { a, b } S = { q0 } F = { q1 } Himpunan { q1, q2 } merupakan NFA

Tabel Transisi δ

a

b

q0 {q1, q2 }

q0

q1

q1

q0

q2

q2

q1

q0 mendapat input a dengan 2 transisi state { q1, q2 }

NFA ⇒ Jika state satu mempunyai 2 transisi dengan input yang sama Jika mendapat input “bababaaa”, apakah diterima oleh mesin ? δ ( q0, bababaaa ) = δ ( q0, ababaaa ) = δ ( {q1, q2}, babaaa ) * Jika diambil q1………. δ ( q0, abaaa ) = δ ( {q1, q2}, baaa ) = δ ( q1, aaa ) = δ ( q1, aa ) = δ (q1, a ) = q1 “ dterima oleh mesin & L ( m ) “

REDUKSI JUMLAH STATE PADA FINITE STATE AUTOMATA

REDUKSI JUMLAH STATE PADA FINITE STATE AUTOMATA

TAHAPAN REDUKSI : 1. Hapus semua state yang tidak dapat dicapai dari state awal. 2. Buatlah semua pasangan state ( p, q ) yang distinguishable, dimana P € F dan q € f. Catatlah pasangan state – state tersebut. 3. Untuk semua state lakukan pencarian state yang distinguishable dengan aturan untuk semua ( p, q )dan a € Σ, hitunglah δ ( p, a ) = pa dan δ ( q, a) = qa. Jika pasangan ( pa, qa ) telah tercatat sehingga distinguishable maka pasangan ( p, q ) juga dimasukkan sebagai distinguishable. 4. Dari hasil No. (3), distinguishable dapat pasangan state – state distringuishable. Pasangan – pasangan state lain yang tidak termasuk ke dalam state distinguishable tersebut, sisanya dapat ditentukan sebagai state yg indistinguishable. 5. Beberapa state yang saling indistinguishable dapat digabungkan ke dalam satu state. 6. Sesuaikan transisi dari dan ke state – state gabungan tersebut.

distringuishable ⇒ dapat dibedakan indistringuishable ⇒ tidak dapat dibedakan

2 buah state p dan q dari DFA dikatakan indistrnguishable Jika → δ ( q, w ) € F sedang δ ( p, w ) € F → δ ( q, w ) € F sedang δ ( p, w ) € F untuk semua w € Σ State p dan q dikatakan distinguishable jika ada string w € Σ δ ( q, w ) € F sedang δ ( p, w ) € F contoh : o o

qo

1

1

q1

o q2

0.1 q4 1

o o

1

q3

Lakukan reduksi jumlah state terhadap mesin tersebut

Tahap – tahap yang dilakukan untuk reduksi jumlah state adalah 1. Tidak ada state yang tak dicapai dari state awal 2. Catat state – state yang distinguishable sbb : pasangan ( q0, q4 ), ( q1, q4 ) ( q2, q4 ) dan ( q3, q4 ) dicatat dari → q0, q1, q2, q3 bukan elemen final state , sedangkan q4 € F 3. Tentukan pasangan state lain : → pasangan ( q0, q1 ) : δ ( q0, 1) = q3 dan δ ( q1, 1) = q4 sedangkan ( q3, q4 ) distinguishable, maka ( q0, q1 ) juga distinguishable → pasangan ( q0, q2 ) : δ ( q0, 1) = q3 dan δ ( q2, 1) = q4 sedangkan ( q3, q4 ) distinguishable, maka ( q0, q2 ) juga distinguishable → pasangan ( q0, q3 ) : δ ( q0, 1) = q3 dan δ ( q3, 1) = q4 sedangkan ( q3, q4 ) distinguishable, maka ( q0, q3 ) juga distinguishable

4. Periksa semua pasangan state : State – state distinguishable q4 ),

: ( q0, q4 ), ( q1, q4 ), ( q2, q4 ), ( q3, ( q0, q1 ), ( q0, q2 ), ( q0, q3 )

State – state indistinguishable : ( q1, q2 ), ( q1, q3 ), ( q2, q3 ) 5. q1 indistinguishable q2, q2 indistinguishable dengan q3, maka q1, q2, q3 saling indistinguishable dan dapat dijelaskan dalam satu state 6. Gambar setelah reduksi jumlah state qo

q123

0, 1

q4

0 1

0,1

Latihan Soal 1. Lakukan Reduksi jumlah state terhadap mesin berikut : qo

q1

o

q3 0,1 1

q2

q4

1

q5

0 1 0

0 1 0,1

Tahap – tahap yang dilakukan untuk reduksi jumlah state adalah sbb : 1. Ada state yang tak dicapai dari state awal yaitu q5…(dihapus) 2. Distinguishable :…..( q0, q3 ), ( q2, q4 ), ( q1, q4 ) ( q2, q3 ), ( q0, q4 ), ( q1, q3 ) q0, q1, q2, € F q3, q4 € F

3. State – state distinguishable yang lain : ( q0, q1 ) → δ ( q0, 1 ) = q3 δ ( q1, 1 ) = q4

( q3, q4 )

( q0, q2 ) → δ ( q0, 1 ) = q3 δ ( q2, 1 ) = q4

( q3, q4 )

4. Distinguishable : ( q0, q3 ), ( q2, q4 ), ( q1, q4 ), ( q2, q3 ) ( q0, q4 ), ( q1, q3 ), ( q0, q1 ), ( q0, q2 ) Indistinguishable : ( q1, q2 ), ( q3, q4 ) 5. q1 dan q2 saling indistinguishable q2 dan q3 saling indistinguishable 6.

0 qo

0

1

1 q123

0.1 1

q4

2.

0 q1

0

q3

0

1

qo

1

1

q5 0,1 q2

0,1 q4 1

...