PENDAHULUAN Teori Bahasa

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

a qo

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


q30,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


0

6. qo

0

1

1 q123


0.1 1

q4


0

2. q1

0

q3

0

1

qo

1

1

q5 0,1 q2

0,1 q4

1

0 q6

0,1 Tahap – tahap yang dilakukan untuk reduksi jumlah state adalah sbb : 1. Tidak ada state yang tak dicapai dari state awal 2. Distinguishable:( q0, q1 ), ( q0, q3 ), ( q2, q4 ), ( q2, q6 ), ( q5, q4 ), ( q5, q6 ) q0, q4, q6 € F q1, q2, q3, q5 € F

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

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

saling indistinguishable
0.1

6. qo

0.1

q123 5

0.1

q4 6

0.1

Tugas 1. Gambarkan diagram transisi dari Deterministic Finite Automata berikut Q = { q 0, q 1, q 2 } ∑ = { a,b } S = q0 F = {q0 } Fungsi transisi dari DFA tersebut δ

a

b

q0

q1

q2

q1

q2

q0

q2

q2

q2

2. Bila L(M) adalah bahasa yang diterima oleh Deterministic Finite Automata pada gambar di bawah, tentukan string berikut termasuk dalam L(M ) a a, b qo q1 q1 b a. aaa b. bbbb c. abba

PERTEMUAN 3 EKIVALENSI NFA KE DFA

Tahapan Pengubahan Non-Deterministic Finite Automata ke Deterministic Finite Automata Dari sebuah mesin Non-Deterministic Finite Automata dapat dibuat mesin DFA yang ekivalen. Ekivalen artinya mampu menerima bahasa yang sama . * Suatu DFA dapat dipandang sebagai kasus khusus (subset) dari NFA. • Jelas bahwa kelas bahasa yang diterima oleh DFA juga akan diterima oleh DFA • Namun ternyata DFA juga dapat mensimulasikan NFA; yaitu untuk setiap NFA kita dapat membuat DFA yang ekivalen • Dapat dibuktikan bahwa DFA dan NFA adalah ekivalen, sehingga dapat disebut FA saja Simulasi NFA oleh DFA • Cara simulasi NFA oleh DFA adalah dengan membuat state DFA berkorespondensi dengan set state di NFA • DFA yang dibentuk mencatat semua state yang mungkin pada NFA setelah membaca input tertentu

EKIVALENSI NFA ke DFA Contoh : Mesin NFA
0


1 0.1

q0

q1

1

Konfigurasi mesin Tabel Transisi δ

0

q0 { q0, q1 } q1

φ

Q = ( { q0 }, { q1} ) 1

Σ = { 0, 1 }

q1

S = q0

{ q0, q1 }

F = q1

Telusuri setiap state yang ada dimulai dari { q0 } :
State { q0 } bila memperoleh input o menjadi state { q0, q1 }
State { q0 } bila memperoleh input 1 menjadi state { q1 }

{ q1 } 1 qo 0 {qo, q1}


State { q1 } - State { q1 } bila memperoleh input o menjadi state φ - State { q1 } bila memperoleh input 1 menjadi state { q0, q1 }
State { q0, q1 } bila memperoleh input o menjadi state { q0, q1 } diperoleh dari δ ( q0, 0 ) = { q0, q1 }

δ ({ q0, q1}, 0) = { q0, q1 }

δ ( q1, 0 ) = φ
State { q0, q1 } bila memperoleh input 1 menjadi { q0, q1 } diporoleh dari δ ( q0, 1 ) = { q1 }

digabung

δ ( q1, 1 ) = { q0, q1 } δ ({ q0, q1 }, q1) = { q0, q1}

Hasil setelah penelusuran { q1 }, { q0 }, { q0, q1 } q1 1

0 φ

qo

1 0

0,1

δ ( φ, 0 ) = φ δ ( φ, 1 ) = φ

{ q0, q1}

F = ({ q1 }, { q0, q1 }) 0.1 Hasilnya adalah mesin DFA Tabel Transisi

Konfigurasi Mesin

δ

0

1

Q = ( qo, { q0, q1 }, q1, φ )

q0

{ q0, q1 }

q1

q1

φ

ε = { 1,0 }

{ q0, q1 }

{ q0, q1 } { q0, q1 } φ

φ

{ q0, q1 } φ

S = q0 F = ( q1, { q0, q1 } )

Tugas 1. Buatlah DFA yang ekuivalen dengan NFA berikut Q = { p, q, r, s} ∑ = { 0, 1} S=p F = {s} Fungsi transisinya dinyatakan dalam tabel transisi berikut

δ

0

1

p

p, q

p

q

r

r

r

s

-

s

s

s

2. Buatlah DFA yang ekuivalen dengan NFA berikut Q = { p, q, r, s} ∑ = { 0, 1} S=p F = {q, s} Fungsi transisinya dinyatakan dalam tabel transisi berikut δ

0

1

p

p, s

p

q

r

q, r

r

s

p

s

-

p

PERTEMUAN 4 Ekivalensi NFA ε - MOVE ke NFA TANPA

ε - MOVE

NFA ε – MOVE NFA ε – MOVE adalah mesin NFA yang diperbolehkan mengubah state tanpa membaca input. Disebut dengan transisi ε karena tidak bergantung pada suatu input ketika melakukan transisi. Contoh NFA ε - MOVE

- q0 tanpa membaca input dapat berpindah ke q1 - q1 tanpa membaca input dapat berpindah ke q2 - q4 tanpa membaca input dapat berpindah ke q1 ε - closure adalah himpunan state – state yang dapat dicapai dari suatu state tanpa membaca input

ε - closure ( q0 ) = { q0, q1, q2 } ε - closure ( q1 ) = { q1, q2 } ε - closure ( q2 ) = { q2 } ε - closure ( q3 ) = { q3 } ε - closure { q4 ) = { q1, q2, q4 } Pada suatu state yang tidak memiliki transisi ε maka ε - closureny adalah state itu sendiri.

EKIVALENSI NFA ε - MOVE KE NFA tanpa ε - MOVE Tahapan – tahapan / langkah ekivalensi NFA dengan ε - move ke NFA tanpa ε - Move : 1. Buat tabel Transisi NFA ε - Move 2. Tentukan ε - Closure untuk setiap state 3. Carilah setiap fungsi hasil perubahan dari NFA ε - Move ke NFA tanpa ε - Move dengan rumus : δ’ ( state, input ) = ε - closure ( δ (εε - closure (state), input )) 4. Berdasarkan hasil no. 3 buat tabel transisi & diagram transisi NFA tanpa ε - Move yang ekivalensi dengan NFA ε - Move ε

5. Tentukan state akhir untuk NFA tanpa ε - Move tersebut, yaitu state – state akhir semua & tambah dengan state – state yang Σ - closurenya menuju ke salah satu dari state akhir semula. Contoh mesin NFA ε - Move ⇒

Buat Ekivalensi NFA ε - Move ke NFA tanpa ε - Move

1.

2.

Tabel Transisi NFA ε - Move δ

a

q0

φ

φ

q1

q2

q3

q2

φ

φ

q3

φ

φ

b

ε - closure ( q0 ) = { q0, q1 } ε - closure ( q1 ) = { q1 } ε - closure ( q2 ) = { q2 } ε - closure ( q3 ) = { q3 }

3. δ’ ( state, input ) = ε - closure ( δ (εε - closure (state), input )) δ’ ( q0, a ) = ε - closure ( δ (εε - closure (q0), a )) = ε - closure ( δ ( { q0, q1 }, a )) = ε - closure ( q2 ) = { q2 } δ’ ( q0, b ) = ε - closure ( δ (εε - closure (q0), b )) = ε - closure ( δ ( { q0, q1 }, b )) = ε - closure ( q3 ) = { q3 } δ’ ( q1, a ) = ε - closure ( δ (εε - closure (q1), a )) = ε - closure ( δ ( { q1 }, a )) = ε - closure ( q2 ) = { q2 } δ’ ( q1, b ) = ε - closure ( δ (εε - closure (q1), b )) = ε - closure ( δ ( { q1 }, b )) = ε - closure ( q3 ) = { q3 }

δ’ ( q2, a ) = ε - closure ( δ (εε - closure (q2), a )) = ε - closure ( δ ( { q2 }, a )) = ε - closure ( φ ) =φ δ’ ( q2, b ) = ε - closure ( δ (εε - closure (q2), b )) = ε - closure ( δ ( { q2 }, b )) = ε - closure ( φ ) =φ δ’ ( q3, a ) = ε - closure ( δ (εε - closure (q3), a )) = ε - closure ( δ ( { q3, a } ) = ε - closure ( φ ) =φ δ’ ( q3, b ) = ε - closure ( δ (εε - closure (q3), b )) = ε - closure ( δ ( { q3 }, b )) = ε - closure ( φ ) =φ

4.

NFA tanpa ε - Move

Tabel Transisi δ’

5. a

b

a q0

q0 q2 q3

q2

q1 q2 q3 q2

φ

φ

q3

φ

φ

a b

q1

b q3

Tugas 1. Buatlah NFA tanpa ε-move yang ekuivalen dengan NFA ε-move pada gambar di bawah ini , (∑ = {0,1,2}) 2 0

q0

1

ε

q1

ε

q2

2. Buatlah NFA tanpa ε-move yang ekuivalen dengan NFA ε-move pada gambar di bawah ini , (∑ = {0,1,2}) 0

q0

ε q1

1

Ekspresi Reguler Pertemuan 5

5.1. Penerapan Ekspresi Reguler (ER) • • • •

Sebuah bahasa dinyatakan reguler jika terdapat Finite State Automata (FSA) yang dapat menerimanya. Bahasa yang diterima oleh suatau FSA dapat dinyatakan secara sederhana dengan Ekspresi Reguler ER. ER memberikan suatau pola (pattern) atau template untuk untai (string) dari suatu bahasa. Banyak masalah pada perancangan perangkat lunak yang dapat disederhanakan dengan melakukan pengubahan notasi ER ke dalam implementasi komputer dari FSA yang bersangkutan.

5.2. Notasi ER Nama

Symbol

asterik

*

‘plus’ atau ‘union’ ‘plus’

+ Atau ∪

titik

+

.

Tabel 5.1. Notasi ER Keterangan Bisa tak muncul, bisa juga muncul berhingga kali (0 sampai n) Gabungan

Tanda ‘plus’ pada posisi superscript, berarti minimal muncul satu kali (1-n) Berarti konkatenasi. Biasanya titik bisa dihilangkan. Misalnya a.b = ab

Ekspresi ER ab*cc 010*

Table 5.2. Contoh ER String yang dibangkitkan abcc, abbcc, abbbcc, acc 01, 010, 0100, 01000

a*d a+d a*∪b* a∪b (a∪b)* 01*+0

d, ad, aad, aaad ad, aad, aaad a, b, aa, bb, aaa, bbb, a, b a, b, aa, ab, bba, aaa, bbb, 00, 010, 0110, 01110, 011110

5.3. Hubungan ER dan FSA • • •

Untuk setiap ER, ada satu Non-Deterministik Finite Automata dengan transisi ε (NFA ε-move) Sementara untuk Deterministik Finite Automata DFA ada satu ER dari bahasa yang diterima Sederhananya kita dapat membuat satu NFA ε-move dari suatu ER

q0

a

q1

ε

q2

b

q3

Gambar 5.1. NFA ε-move untuk ER: ab a q0

ε

q1

b

q2

Gambar 5.2. NFA ε-move untuk ER: a*b

ε

q0

q1

a

q2

ε

ε

q3

ε q4

b

q5

Gambar 5.3. NFA ε-move untuk ER: a∪b

Tentukan ER untuk setiap mesin FSA pada gambar 5.4 dan gambar 5.5. 0 q0

1

q1

1 1

q2

0 Gambar 5.4. Mesin FSA

a q0

a

q1

b

q3

a a q2

b

q4

b Gambar 5.5. Mesin FSA

Hubungan antara NFA, ε-move, DFA, dan ER

NFA NFA ε-move

DFA

ER

Latihan Studi Kasus: 1. kita ingin membuat mesin DFA yang menerima bahasa berupa semua string yang berakhiran dengan ’00’, diketahui Σ=(0,1). Tentukan: ER, Mesin NFA, dan Mesin DFA 2. kita ingin membuat mesin DFA yang menerima bahasa berupa semua string yang memuat minimal dua nol berurutan ’00’, diketahui Σ=(0,1). Tentukan: ER, Mesin NFA, dan Mesin DFA

EKSPRESI REGULAR

EKSPRESI REGULAR Notasi Ekspresi Regular : * Yaitu karakter asterik ; berarti bisa tidak muncul, bisa juga muncul berhingga kali. +

( pada posisi superscript/ diatas ) berarti minimal muncul satu kali

+ atau ∪ berarti union berarti gabungan Contoh Ekspresi Regular 1. ER : ab*cc Contoh string yang dibangkitkan/ dibentuk : abcc, abbcc, abbbcc, abbbbcc, acc 2. ER : 010* Contoh string yang dibentuk : 01, 010, 0100, 01000, 010000 3. ER : a*d String yang dibentuk : d, ad, aad, aaad

4. ER : a+d Contoh string yang dibentuk : ad, aad, aaad 5. ER : a*∪b* ( ‘∪’ berarti atau ) string yang dibentuk : a, b, aa, bb, aaa, bbb, aaaa, bbbb 6. ER : ( a ∪ b ) berarti atau ‘ ∪ ‘ string yang dibentuk : a, b 7. ER : ( a ∪ b )* string yang dibentuk : a, b, ab, ba, abb, bba, aaaa, bbbb notasi ∪ kadang ditulis + 8. ER : 01* + 0 string yang dibentuk : 0, 01, 011, 0111, 01111

Hubungan Ekspresi Regular & FSA qo

q1

1.

q2

ε

a

q3

b

ER ; ab


qo a

ε

b

q1

q2

2. ER ; a*b 3.

a

qo

q1

ER : a ∪ b b q2

4.

qo

q1

0

ER ; 010*

q2

1

0

5.

qo

0

0,1

q1

q2

ER ; 0 ( 1 ∪ 0 )

0,1 6.

qo

0

q1

ER ; 0 ( 1 ∪ 0 ) * 7.

0

qo

q1

1

0

ER ; 01*0 8.


0 qo

0 1

ER ; 0*10* 9.

q0

ER ; a*

a

q1

q2

10.

a qo

q1

b ER ; a ( ba )* 11.

a q0

q1

b ER ; ( ab ) * 12. qo

1

q1

0 0

ER ; 01*∪10*11*

1

q2

1

Aturan Produksi Untuk Finite State Automata (FSA) Pertemuan 6

6. 1. Aturan Produksi Bahasa Reguler • Sebuah otomata berhingga menspesifikasikan sebuah bahasa sebagai himpunan semua untai yang menggerakkannya dari state awal ke salah satu state yang diterimanya (himpunan state akhir) • Misalkan untuk sebuah ER: a(a*∪b*)b. Selain dengan ER, kita dapat mengkonstruksi aturan-aturan produksi untuk suatu tata bahasa reguler. • Kita ingat juga batasan aturan produksi untuk bahasa reguler: α→β (dibaca: α menghasilkan β) dimana α adalah sebuah simbol variabel, dan β maksimal memiliki sebuah simbol variabel yang terletak di paling kanan (bila ada) • α dan β dapat berupa simbol terminal atau simbol nonterminal (variabel)

• Simbol variabel (non-terminal adalah simbol yang masih bisa diturunkan, sedangkan simbol terminal sudah tidak bisa diturunkan lagi. • Simbol terminal biasanya dinyatakan dengan huruf kecil, misal: a, b, c. • Simbol non-terminal (variabel) biasanya dinyatakan dengan huruf besar, misal: A, B, C. • Suatu tata bahasa (grammer) didefinisikan dengan empat tupel (G={V, T, P, S}), dimana: v = himpunan simbol variabel T = himpunan simbol terminal P = kumpulan aturan produksi S = simbol awal

a ε

q2 b

q0

a

q1

q3 b

ε q3 Gambar 6.1. Mesin FSA

b

Dari gambar 6.1., kumpulan aturan produksi yang kita peroleh dapat dituliskan sbb: S → aE E→A|B A → aA | B B → bB | b Secara formal, tata bahasa (grammer) yang diperoleh dari otomata pada gambar 6.1. adalah: V = {S, E, A, B} T = {a, b} P = {S → Ae, E → A | B, A → aA | B, B → bB | b} S=S

6.2. Mengkonstruksi Aturan Produksi dari Suatu FSA • Dalam mengkonstruksi aturan produksi tata bahasa reguler dari suatu FSA, yang menjadi perhatian kita adalah state-state yang dapat menuju ke state akhir. • Mesin FSA pada gambar 6.1, memiliki simbol input a dan b. simbol tersebut akan menjadi terminal pada aturan produksi yang akan kita bentuk. • Misalkan kita tentukan simbol awal adalah S, state awal q0, dari q0 mendapat input a menjadi q1.Aturan produksi yang dapat ditulis adalah: S→aE • E dapat kita identikkan denga q1, lebih tepatnya adalah bagian yang belum terbangkitkan mulai dari q1.

• Kita dapat menambahkan simbol variabel baru setiap kali kita perlukan. • Dari q1mendapat tramsisi-e (tanpa menerima input) ke q2 dan q3, kita tuliskan: E→A E→B • Jika kita identikkan q2 sebagai A, dan q3 sebagai B; dari q2 mendapat input a tetap ke q2; dari q3 mendapat input b tetap ke q3; bisa kita tuliskan: A→ aA B → bB

• Selanjutnya kita lihat: dari q2 memberikan input b ke q4; dari q3 memberikan input b ke q4; sementara q4 merupakan state akhir, maka bisa dituliskan: A→ b B→b • Kumpulan aturan prosuksi yang kita peroleh adalah sbb: S→ aE E → AB A → aAB B → bBb

• Secara formal, tata bahasa yang diperoleh dari otomata pada gambar 6.1 adalah sbb: V = {S, E, A, B} T = {a, b} P = {S→aE; E → AB; A → aAB; B → bBb} S=S

6.3. FSA Untuk Suatu Tata Bahasa Reguler • Bila sebelumnya dari suatu diagram transisi FSA kita dapat membuat aturan-aturan produksinya, sebaliknya kita juga dapat mengkonstruksi diagram transisi FSA untuk suatu tata bahasa teguler yang diketahui aturan-aturan produksinya. • Misalnya terdapat tata bahasa reguler dengan aturan produksi sbb: S→ aB bAε A → abaS B → babS FSA dari aturan produksi diatas, seperti yang ditunjukkan pada gambar 6.2. berikut

b a q0

q1

b

q2

a

q3

b q4

a

a q5

b

q6

Gambar 6.2. FSA dari suatu regular grammer

ATURAN PRODUKSI

ATURAN PRODUKSI α
β α menurun β α menghasilkan β α atau β bisa berupa simbol variabel terminal atau non terminal. Gramer didefinisikan dengan 4 tipe ( G = { VN, VT, P, S } ) VN : himpunan simbol variabel non terminal VT : himpunan simbol variabel terminal P : himpunan aturan produksi S : simbol awal q2


a

Contoh mesin FSA qo

q1

ε

b

a ε

q3 b




b

q4

Aturan produksi dari mesin FSA  S
aE S adalah q0

q1 didefinisikan dengan E

E adalah q1

q1 identik dengan E q0 identik dengan S

 dari q1 tanpa mendapat input menuju q2 dan q3 E→A

A identik q2

E→B

B identik q3

 dari q2 mendapat input a tetap ke q2 dari q3 mendapat input b tetap ke q3 A → aA B → bB  dari q2 mendapat input b ke q4 dari q3 mendapat input b ke q4

A→ b B→b Karena q4 adalah final state yang tidak memiliki busur keluar atau keluaran maka q4 tidak didefinisikan atau diabaikan Kumpulan Aturan Produksi S → aE E → A|B A → aA | b B → bB | b ‘ | ‘ berarti atau VN = { S, E, A, B } S=S VT = { a, b } P = { S → aE, E →A | B, A →aA | b, B →bB | b }

Finite State Automata (FSA) Dengan Output Pertemuan 9

7.1. Mesin Moore • Suatu keterbatasan dari FSA yang sudah dipelajari sebelumnya adalah: keputusannya terbatas pada diterima atau ditolak. Otomata tsb biasa disebut dengan accepter (dalam hal ini FSA). • Kita dapat mengkonstruksi sebuah FSA yang memiliki keputusan beberapa keluaran (output), dalam hal ini otomata tersebut dikenal sebagai transducer. • Pada mesin Moore, output akan berasosiasi dengan state.

Mesin Moore didefinisikan dalam 6 tupel, yaitu: M=(Q, Σ, δ, S, ∆, λ) Dimana: Q Σ δ S ∆ λ

= = = = = =

himpunan state himpunan simbol input fungsi transisi state awal, dimana S∈ ∈Q himpunan output fungsi output untuk setiap output

Contoh Mesin Moore Misalnya kita ingin memperoleh sisa pembagian (modulus) suatu bilangan dengan 3, dimana input dinyatakan dengan biner. Konfigurasi mesinnya adalah sbb: Q = {q0, q1, q2} Σ = {0, 1} S = q0 ∆ = {0, 1, 2} untuk output pada kasus mod dengan 3, kemungkinan sisa pembagiannya adalah 1, 2 atau 3 λ = q0=0, q1=1, q2=2

0 q0 0

1 1 1

q1

0

q2

0 1

2

Gambar 7.1. Mesin Moore untuk MOD 3 Coba buktikan untuk: • 5 MOD 3. • 10 MOD 3 (Input nya harus dirubah dulu kedalam biner)

7.2. Mesin Mealy • Bila output pada mesin Moore berasosiasi dengan state, maka output pada mesin Mealy akan berasosiasi dengan transisi. • Mesin Mealy sendiri didefinisikandalam 6 tupel, yaitu: M=(Q, Σ, δ, S, ∆, λ) Dimana: Q = himpunan state Σ = himpunan simbol input δ = fungsi transisi S = state awal, dimana S∈ ∈Q ∆ = himpunan output λ = fungsi output untuk setiap output

Contoh Mesin Mealy Mesin ini akan mengeluarkan output menerima ‘Y’ atau menolak ’T’ suatu masukan biner. Dengan ketentuan: mesin akan mengeluarkan output ‘Y’ bila menerima untai yang memiliki dua simbol berurutan yang sama, atau secara formal dalam ER: (0+1)*(00+11) Konfigurasi mesinnya adalah sbb: Q = {q0, q1, q2} Σ = {0, 1},0 S = q0 ∆ = {Y, T} λ(q0,0)=T; λ(q0,1)=T; λ(q1,0)=Y; λ(q1,1)=T λ(q2,0)=T; λ(q2,1)=Y

0/Y 0/T q0 1/T

q1 0/T

1/T q2

1/Y Gambar 7.2. Contoh Mesin Mealy Coba buktikan untuk input yang diterima: 01011; 01100; 1010100; 10110100; 00; 11; 100; 011; 111; 0101; 0010

7.3.

Ekuivalensi Mesin Mealy

Mesin

Moore

dan

• Dari suatu mesi Moore, dapat dibuat mesin Mealy yang ekuivalen, begitu juga sebaliknya. • State pada mesin Moore dibentuk dari kombinasi state pada Mealy dan banyaknya output. • Untuk mesin Mealy pada gambar 7.2, jumlah state=3; dan jumlah output=2; maka jumlah state pada mesin Moore yang ekuivalen adalah = 6.

• Konfigurasi mesIn Moore yang dibentuk adalah: Q = {q0Y, q0T, q1Y, q1T, q 2 Y, q 2 T} Σ = {0, 1} S = q0 ∆ = {0, 1, 2} λ(q0Y)=Y; λ(q0T)=T; λ(q1Y)=Y; λ(q1T)=T; λ(q2Y)=Y; λ(q2T)=T

1 1 0

q0T T

0

q0T T

0

T

0 1

q0T Y

q0T

0

0

q0T Y

1 q0T

Y

1

1 Gambar 7.3. Mesin Moore yang ekuivalen dengan Mesin Mealy pada gambar 7.2.

• Untuk memperoleh ekuivalensi mesin Mealy dari suatu mesin Moore, caranya lebih mudah, cukup dengan menambahkan label output ke setiap transisi, dan menghapus label output pada setiap state • Konfigurasi mesIn Moore yang dibentuk adalah: Q = {q0, q1, q 2} Σ = {0, 1} S = q0 ∆ = {0, 1, 2} λ(q0,0)=0; λ(q0,1)=1 λ(q1,0)=2; λ(q1,1)=0 λ(q2,0)=1; λ(q2,1)=3

0/0 q0

1/2 1/1 1/0

q1

0/2 q 2 0/1

Gambar 7.4. Mesin Mealy yang ekuivalen dengan Mesin Moore pada gambar 7.1.

FSA (FINITE STATE AUTOMATA)

DENGAN OUTPUT

Mesin Moore dengan 6 Tuple M = (Q, Σ, δ, S, ∆, λ) Q = Himpunan State Σ

= Himpunan simbol input

δ

= Fungsi transisi

S

= State awal, S ∈ Q

∆

= Himpunan output

λ

= Fungsi output untuk setiap state

Contoh : konfigurasi mesin Q = {q0, q1, q2} Σ

= {0, 1)

∆

= {0, 1, 2}

S

= (q0)

λ(q0) = 0 λ(q1) = 1 λ(q2) = 2

1

0 1

q0

0

q1 1

0

q2 0

1

2

5 mod 3 = ? mod → hasil dari sisa pembagian bilangan biner 5 = 101 urutkan state : δ (q0, 101) = δ(q1, 01) = δ (q2, 1) = q2 Berakhir pada q2 λ (q2)= 2 maka 5 mod 3 = 2

Mesin Moore untuk modulus 3


10 mod Bilangan biner 10 = 1010 Urutkan state : δ (q0, 1010) = δ (q1, 010) = δ ( q2, 10) = δ ( q2, 0) = q1 Beakhir pada q1 λ (q1) = 1  MESIN MEALY Dengan 6 tuple M = (Q, Σ, δ, S, ∆, λ )

maka 10 mod 3 = 1

Contoh Mesin Mealy : Konfigurasi mesin Q = {q0, q1, q2}

λ = (q0, 0) = T

Σ = { 0, 1}

λ = (q0, 1) = T

∆ = { Y, T}

λ = (q1, 0) = Y

S = {q0}

λ = (q1, 1) = T λ = (q2, 0) = T λ = (q2, 1) = Y

q1 0/Y

Jika MEsin Mealy menerima input “110101”, apakah diterima oleh mesin tersebut ?

0/T q0

0/T

1/T 1/T

q2 1/Y

δ (q0, 110101) = δ (q2, 10101) T = δ (q2, 0101) = δ (q1, 101) Y T = δ (q2, 01) Y

= δ (q1, 1) = q2 T T

Tidak diterima input 110101, ditolak oleh Mesin Mealy

Contoh soal : 0

0

3

q0

Mesin Moore

0 1

q3

1

1 q4

1 0

- Buat konfigurasi mesin tersebut

4

2 1

q1

0

q2

0

- Jika mesin menerima input “1101011”, output ?

0 1

q5

5 1

δ (q0, 1101011) = δ (q1, 101011) = δ (q3, 01011) 1

3

= δ (q3, 1011) = δ (q4, 011) = δ (q2, 11) = δ (q5, 1) = q5 3

4

2

5

5

Input = 1101011

λ ( q0 ) = 0

Output = 1334255

λ ( q1 ) = 1

Q = {q0, q1, q2, q3, q4, q4}

λ ( q2 ) = 2

Σ = {0, 1}

λ ( q3 ) = 3

∆ = { 0, 1, 2, 3, 4, 5 }

λ ( q4 ) = 4

S = q0

λ ( q4 ) = 4

A

LATIHAN : 1. JIka Mesin Moore pada contoh soal didapat “ 1010101101011 “, Output ?

2. Pada Mesin Moore Modulus 3 → 40 mod 3 ? → 55 mod 3 ? → 73 mod 3 ?

3. Pada mesin Mealy jika input “ 0110011011 “ apakah diterima ?

1. δ (q0, 1010101101011) = δ (q1, 010101101011) = (q2, 10101101011) 1

2

= δ (q5, 0101101011) = δ (q1, 101101011) = δ (q3, 01101011) 5

1

3

= δ (q3, 1101011) = δ (q4, 101011) = δ (q4, 01011) = δ (q2, 101) 3

4

4

= δ (q5, 011) = δ (q1, 11) = δ (q3, 1) = q4 5 Input

1 = 1010101101011

Output = 1251334425134

3

4

2

2. ∗ 40 mod 3 bilangan biner 40 = 101000 urutkan state : δ (q0, 101000) = δ (q1, 01000) = δ (q2, 1000) = δ (q2, 000) = δ (q1, 00) = δ (q1, 0) = q1 Berakhir pada λ (q1)= 1

40 mod 3 = 1

∗

55 mod 3 bilangan biner 55 = 110111 urutkan state : δ (q0, 110111) = δ (q1, 10111) = δ (q0, 0111) = δ (q0, 111) = δ (q1, 11) = δ (q1, 1) = q1 Berakhir pada Q1 λ (q1) = 1 55 mod 3 = 1

∗

73 mod 3 bilangan biner 73 = 1001001 δ (q0, 1001001) = δ (q1, 001001) = δ (q2, 01001) = δ (q1, 1001) = δ (q0, 001) = δ (q0, 01) = δ (q0, 1) = q1 berakhir pada q1 λ (q1) = 1

73 mod 3 = 1

3. Jika input “ 011001101011 ”, apakah diterima ? δ (q0, 011001101011) = δ (q1, 11001101011) = δ (q2, 1001101011) T

T

= δ (q2, 001101011) = δ (q1, 01101011) = δ (q1, 1011) Y

T

T

= δ (q2, 101011) = δ (q2, 01011) = δ (q1, 1011) T

Y

T

= δ (q2, 011) = δ (q1, 11) = δ (q2, 1) = q2 T

T

T

T

Pohon penurunan Pertemuan 10

8.1. Tata Bahasa Bebas Konteks • Bila pada tata bahasa reguler terdapat pembatasan pada ruas kanan atau hasil produksinya, maka pada tata bahasa konteks (context free grammer), selanjutnya kita sebut CFG, tidak terdapat pembatasan hasil produksinya. • Seperti halnya pada tata bahasa reguler, sebuah CFG adalah suaatu cara yang menunjukkan bagaimana menghasilkan untai-untai dalam sebuah bahasa.

Pada saat menurunkan suatu string, simbol-simbol variabel akan mewakili bagian-bagian yang belm terturunkan dari string tersbut. • Pada tata bahasa reguler : bagian yang belum terturunkan tsb selalu terjadi pada suatu ujung. • Pada tata bahasa bebas konteks: bisa terdapat lebih banyak bagian yang belum terturunkan dan bisa terjadi dimana saja. Ketika penurunan itu telah lengkap, semua bagian yang belum terturunkan telah diganti oleh string- string (yang mungkin sja kosong) dari himpunan simbol terminal.

8.2. Parsing • Sebuah pohon (tree) adalah suatu graph terhubung tidak sirkuler, yang memiliki satu simpul (node) / vertex yang disebut akar (root) dan dari Node memiliki lintasan ke setiap simpul. • Pohon penurunan (derivation tree/parse tree) berguna untuk menggambarkan bagaimana memperoleh suatu string (untai) dengan cara menurunkan simbol-simbol variabel (VN) menjadi simbol-simbol terminal (VT). Setiap simbol variabel akan diturunkan menjadi terminal, sampai tidak ada yag belum tergantikan

•

Misalnya, terdapat tata bahasa bebas konteks dengan aturan produksi sbb: S →AB A→aAa B→bBb akan kita gambarkan pohon penurunan untuk memperoleh untai: ‘aabbb’ S A B a

A a

b

B b

B b

Proses penurunan atau parsing bisa dilakukan dengan cara sbb: • Penurunan terkiri (leftmost derivation): Proses Penurunan dimulai dari simbol S, dgn simbol variabel terkiri yang diperluas terlebih dahulu. • Penurunan terkanan (rightmost derivation): Proses penurunan dimulai simbol S, dgn simbol variabel terkanan yang diperluas terlebih dahulu.

Misal, terdapat tata bahasa bebas konteks: S→ aAS | a A→SbAba Untuk memperoleh untai ‘aabbaa’ dari tata bahasa bebas konteks diatas adalah: • Dengan penurunan terkiri: S⇒aAS⇒aSbAS⇒aabAS⇒aabbaS⇒aabbaa • Dengan penurunan terkanan: S⇒aAS⇒aAa⇒aSbAa⇒aabAa⇒aabbaa

S A

a S a

S

b

A b

a a

Gambar 8.2. Pohon Penurunan untuk untai ‘aabbaa’

8.3. Ambiguitas Ambiguitas/kedwiartian terjadi bila terdapat lebih dari satu pohon penurunan yang berbeda untuk memperoleh suatu untai. Misalkan terdapat tata bahasa bebas konteks sb: S→AB A→a B→a Untuk memperoleh untai ‘a’ bisa terdapat dua cara penurunan, yaitu: S⇒A⇒a S⇒B⇒a

Contoh lain, terdapat tata bahasa konteks: S→SbSScSa Coba anda tentukan cara untuk menurunkan untai ‘abaca’. Dan buatkanlah pohon penurunannya.

Pertemuan 11 PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS

Tujuan Melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tidak perlu atau aturan produksi yang tidak berarti. Contoh 1: S
AB | a A
a ♦ Aturan produksi S
AB tidak berarti karena B tidak memiliki penurunan Contoh 2 : S
A A
B B
C C
D D
a|A

Memiliki kelemahan terlalu panjang jalannya padahal berujung pada S
a, produksi D
A juga menyebabkan kerumitan. Cara Penyederhanaan: 1. Penghilangan produksi useless ( tidak berguna ) 2. Penghilangan produksi unit 3. Penghilangan produksi ε Penghilangan Produksi Useless Di sini produksi useless didefinisikan sebagai : * Produksi yang memuat symbol variabel yang tidak memiliki penurunan yang akan menghasilkan terminal-terminal seluruhnya. * Produksi yang tidak akan pernah dicapai dengan penurunan apapun dari simbol awal, sehingga produksi itu redundan ( berlebih )

Contoh : S
aSa | Abd | Bde A
Ada B
BBB | a Maka 1) Aturan Produksi A
Ada, Simbol variabel A tidak memiliki penurunan yang menuju terminal, sehingga bisa dihilangkan 2) Konsekuensi no (1), aturan produksi S
Abd tidak memiliki penurunan Penyederhanaan menjadi: S
aSa | Bde B
BBB | a

• Contoh : S
Aa | B A
ab | D B
b|E C
bb E
aEa Maka : 1) Aturan produksi A
D, simbol variabel D tidak memiliki penurunan. 2) Aturan produksi C
bb, Penurunan dari simbol S, dengan jalan manapun tidak akan pernah mencapai C 3) Aturan Produksi E
aEa, Simbol variabel E tidak memiliki aturan produksi yang menuju terminal 4) Konsekuensi no (3) Aturan produksi B
E, simbol variabel E tidak memiliki penurunan.

maka produksi yang useless: A
D C
bb E
aEa B
E Penyederhanaannya menjadi: S
Aa | B A
ab B
b

• Contoh : S
aAb | cEB A
dBE | eeC B
ff C
ae D
h Analisa : 1) Aturan produksi S
cEB, A
dBE dapat dihilangkan ( E tidak memiliki penurunan) 2) Aturan produksi D
h, redundan Sisa aturan produksi S
aAb A
eeC B
ff C
ae

Analisis lagi B
ff juga redundan, Hasil penyederhanaan menjadi: S
aAb A
eeC C
ae Contoh lain lagi : S
aB A
bcD | dAC B
e | Ab C
bCb | adF | ab F
cFB

Analisis 1) Aturan produksi A
bcD, variabel D tidak memiliki penurunan 2) Konsekuensi no (1), simbol variabel A tidak memiliki penurunan yang menuju terminal (tinggal A
dAC) 3) Konsekuensi no (2), B
Ab tidak memiliki penurunan 4) Simbol variabel F tidak memiliki penurunan yang menuju terminal 5) Konsekuensi no (4), C
adF tidak memiliki penurunan Setelah disederhanakan menjadi: S
aB B
e C
bCb | ab

Contoh lain lagi : S
aBD B
cD | Ab D
ef A
Ed F
dc Analisa 1) Aturan produksi A
Ed, E tidak memiliki penurunan 2) Aturan produksi F
dc, redundan Sisa aturan produksi: S
aBD B
cD | Ab D
ef

Analisa lagi B
Ab, A tidak memiliki penurunan. Hasil penyederhanaan: S
aBD B
cD D
ef

Contoh lagi: S
Abc | ab A
AAA | ε Aturan produksi setelah disederhanakan: S
Abc | ab A
AAA | ε Ingat A
ε juga harus diperhitungkan PRINSIP Setiap kali melakukan penyederhanaan diperiksa lagi aturan produksi yang tersisa, apakah semua produksi yang useless sudah hilang.

Penghilangan Produksi Unit Produksi dimana ruas kiri dan kanan aturan produksi hanya berupa satu simbol variabel, misalkan: A
B, C
D. Keberadaannya membuat tata bahasa memiliki kerumitan yang tak perlu. Penyederhanaan dilakukan dengan melakukan penggantian aturan produksi unit. Contoh: S
Sb S
C C
D C
ef D
dd

Dilakukan penggantian berturutan mulai dari aturan produksi yang paling dekat menuju ke penurunan terminal-terminal (‘=>’ dibaca ‘menjadi’): C
D => C
dd S
C => S
dd | ef Sehingga aturan produksi setelah penyederhanaan: S
Sb S
dd | ef C
dd C
ef C
dd

Contoh lain: S
A S
Aa A
B B
C B
b C
D C
ab D
b • Penggantian yang dilakukan : C
D => C
b B
C => B
b | ab, karena B
b sudah ada, maka cukup dituliskan B
ab A
B => A
ab | b S
A => ab | b

Sehingga aturan produksi setelah penyederhanaan: S
ab | b S
Aa A
ab | b B
ab B
b C
b C
ab D
b

Contoh lagi: S
Cba | D A
bbC B
Sc | ddd C
eAn | f | C D
E | SABC E
gh

Penggantian yang dilakukan: D
E menjadi D
gh C
C , kita hapus S
D menjadi S
gh | SABC Sehingga aturan produksi setelah penyederhanaan: S
Cba | gh | SABC A
bbC B
Sc | ddd C
eA | f D
gh | SABC E
gh

Penghilangan Produksi ε Produksi ε adalah produksi dalam bentuk α
ε atau bisa dianggap sebagai produksi kosong ( empty ). Penghilangan produksi ε dilakukan dengan melakukan penggantian produksi yang memuat variabel yang bisa menuju produksi ε, atau biasa disebut nullable. Prinsip penggantiannya bisa dilihat kasus berikut: S
bcAd A
ε A nullable serta A
ε satu-satunya produksi dari A, maka variabel A bisa ditiadakan, hasil penyederhanaan tata bahasa bebas konteks menjadi: S
bcd

Tetapi bila kasusnya: S
bcAd A
bd | ε A nullable, tapi A
ε bukan satu-satunya produksi dari A, maka hasil penyederhanaan: S
bcAd | bcd A
bd

Contoh lagi, terdapat tata bahasa bebas konteks: S
Ab | Cd A
d C
ε Variabel yang nullable adalah variabel C. Karena penurunan C
ε merupakan penurunan satusatunya dari C, maka kita ganti S
Cd menjadi S
d. Kemudian produksi C
ε kita hapus. Setelah penyederhanaan menjadi: S
Ab | d A
d

Contoh lain lagi: S
dA | Bd A
bc A
ε B
c Variabel yang nullable adalah variabel A. A
ε bukan penurunan satu-satunya dari A ( terdapat A
bc ), maka kita ganti S
dA menjadi S
dA | d . A
ε kita hapus. Setelah penyederhanaan : S
dA | d | Bd A
bc B
c

Contoh tata bahasa bebas konteks: S
AaCD A
CD | AB B
b|ε C
d|ε D
ε Variabel yang nullable adalah variabel B, C, D. Kemudian dari A
CD, maka variabel A juga nullable ( A
ε ). Karena D hanya memilki penurunan D
ε, maka kita sederhanakan dulu: S
AaCD => S
AaC A
CD => A
C D
ε kita hapus

Selanjutnya kita lihat variabel B dan C memiliki penurunan ε, meskipun bukan satu-satunya penurunan, maka dilakukan penggantian: A
AB => A
AB | A | B S
AaC => S
AaC | aC | Aa | a B
ε dan C
ε kita hapus Setelah penyederhanaan: S
AaC | aC | Aa | a A
C | AB | A | B B
b C
ε

Variabel yang nullable adalah A, B, C. Dari S
AB, maka S juga nullable. Kita lakukan penggantian: A
aCa => A
aa B
bA => B
bA | b B
BB => B
BB | B A
abB => A
abB | ab S
AB => S
AB | A | B | ε C
ε, B
ε, A
ε dihapus *Perhatikan untuk penggantian S
AB kita tetap mempertahankan S
ε, karena S merupakan simbol awal. Ini merupakan satu-satunya perkecualian produksi ε yang tidak dihapus, yaitu produksi ε yang dihasilkan oleh simbol awal.

Hasil akhir dari penyederhanaan: S
AB | A | B | ε A
abB | ab | aa B
bA | b | BB | B Contoh tata bahasa bebas konteks: S
aAb A
aAb | ε Hasil penyederhanaan: S
aAb | ab A
aAb | ab

Contoh tata bahasa bebas konteks: S
ABaC A
BC B
b|ε C
D|ε D
d Hasil penyederhanaan: S
ABaC | BaC | AaC | ABa | aC | Aa | Ba | a | C | BC B
b C
D D
d

A
B

Prakteknya ketiga penyederhanaan tersebut dilakukan bersama pada suatu tata bahasa bebas konteks, yang nantinya menyiapkan tata bahasa bebas konteks tersebut untuk diubah kedalam suatu bentuk normal Chomsky. Urutan penghapusan aturan produksi : 1) Hilangkan produksi ε 2) Hilangkan produksi unit 3) Hilangkan produksi useless

Contoh : S
AA | C | bd A
Bb | ε B
AB | d C
de Hilangkan produksi ε, sehingga menjadi: S
A | AA | C | bd A
Bb B
B | AB | d C
de Selanjutnya penghilangan produksi unit menjadi: S
Bb | AA | de | bd A
Bb B
AB | d C
de

Penghilangan produksi unit bisa menghasilkan produksi useless. Terakhir dilakukan penghilangan produksi useless: S
Bb | AA | de | bd A
Bb B
AB | d Hasil akhir aturan produksi tidak lagi memiliki produksi ε, produksi unit, maupun produksi useless.

PERTEMUAN 12

BENTUK NORMAL CHOMSKY

Pengertian Bentuk Normal Chomsky • Bentuk normal Chomsky / Chomsky Normal Form (CNF) merupakan salah satu bentuk normal yang sangat berguna untuk tata bahasa bebas konteks ( CFG ). Bentuk normal Chomsky dapat dibuat dari sebuah tata bahasa bebas konteks yang telah mengalami penyederhanaan yaitu penghilangan produksi useless, unit, dan ε. Dengan kata lain, suatu tata bahasa bebas konteks dapat dibuat menjadi bentuk normal Chomsky dengan syarat tata bahasa bebas kontesk tersebut: 1. Tidak memiliki produksi useless 2. Tidak memiliki produksi unit 3. Tidak memiliki produksi ε Aturan produksi dalam bentuk normal Chomsky ruas kanannya tepat berupa sebuah terminal atau dua variabel non terminal. Misalkan: A
BC A
b B
a C
BA | d

Pembentukan Bentuk Normal Chomsky • Langkah-langkah pembentukan bentuk normal Chomsky secara umum sebagai berikut: 1. Biarkan aturan produksi yang sudah dalam bentuk normal Chomsky 2. Lakukan penggantian aturan produksi yang ruas kanannya memuat simbol terminal dan panjang ruas kanan > 1 3 Lakukan penggantian aturan produksi yang ruas kanannya memuat > 2 simbol variabel Non Terminal 4 Penggantian-penggantian tersebut bisa dilakukan berkali-kali sampai akhirnya semua aturan produksi dalam bentuk normal Chomsky 5 Selama dilakukan penggantian, kemungkinan kita akan memperoleh aturan-aturan produksi baru, dan juga memunculkan simbol-simbol variabel baru

Contoh, tata bahasa bebas konteks ( kita anggap tata bahasa bebas konteks pada bab ini sudah mengalami penyederhanaan ): S
bA | aB A
bAA | aS | a B
aBB | bS | b Aturan produksi yang sudah dalam bentuk normal Chomsky: A
a B
b Dilakukan penggantian aturan produksi yang belum bentuk normal Chomsky (‘=>’ bisa dibaca berubah menjadi): S
bA => S
P1A S
aB => S
P2B A
bAA => A
P1AA => A
P1P3 A
aS => A
P2S B
aBB => B
P2BB => B
P2P4 B
bS => B
P1S

Terbentuk aturan produksi dan simbol variabel baru: P1
b P2
a P3
AA P4
BB Hasil akhir aturan produksi dalam brntuk normal Chomsky : A
a B
b S
P1A S
P2B A
P1P3 A
P2S B
P2P4 B
P1S P1
b P2
a P3
AA P4
BB

Contoh, tata bahasa bebas konteks: S
aB | CA A
a | bc B
BC | Ab C
aB | b Aturan produksi yang sudah dalam bentuk normal Chomsky : S
CA A
a B
BC C
b Penggantian aturan produksi yang belum dalam bentuk normal Chomsky: S
aB => S
P1B A
bc => A
P2P3 B
Ab => B
A P2 C
aB => C
P1B

• Terbentuk aturan produksi dan simbol variabel baru: P1
a P2
b P3
c Hasil akhir aturan produksi dalam bentuk normal Chomsky : S
CA A
a B
BC C
b S
P1B S
P2P3 B
A P2 C
P1B P1
a P2
b P3
c

Contoh, tata bahasa bebas konteks : S
aAB | ch | CD A
dbE | eEC B
ff | DD C
ADB | aS D
i E
jD Aturan produksi yang sudah dalam bentuk normal Chomsky : S
CD B
DD D
i Penggantian aturan produksi: S
aAB => S
P1P2 S
ch => S
P3P4 A
dbE => A
P5P6 A
eEC => A
P8P9 B
ff => B
P10P10 C
ADB => C
AP11 C
aS => C
P1S E
jD => E
P12D

Terbentuk aturan produksi baru: P1
a P2
AB P3
c P4
h P5
d P6
P7E P7
b P8
e P9
EC P10
f P11
DB P12
j

Hasil akhir dalam bentuk normal Chomsky: S
CD B
DD D
i S
P1P2 S
P3P4 A
P5P6 A
P8P9 B
P10P10 C
AP11 C
P1S E
P12D P1
a P2
AB P3
c P4
h P5
d P6
P7E P7
b P8
e P9
EC P10
f P11
DB P12
j

PERTEMUAN 13 PENGHILANGAN REKURSIF KIRI

Aturan Produksi Rekursif Kanan Aturan Produksi yang rekursif memilki ruas kanan (hasil produksi) yang memuat simbol variabel pada ruas kiri. Sebuah aturan produksi dalam bentuk: Aturan Produksi Rekursif Kanan bentuk umum : A
βA merupakan aturan produksi yang rekursif kanan β=(V∪T)* ∪ atau kumpulan simbol variabel dan terminal Contoh aturan produksi yang rekursif kanan: S
dS B
adB Aturan Produksi Rekursif Kiri bentuk Umum: A
Aβ Merupakan aturan produksi yang rekursif kiri, contohnya: S
Sd B
Bad

Tahapan Penghilangan Rekursif Kiri Langkah-langkah penghilangan rekursif kiri: 1. Pisahkan aturan produksi yang rekursif kiri dan yang tidak, misal: Aturan produksi yang rekursif kiri: A
Aα1 | Aα2 | Aα3 | ... . Aαn Aturan produksi yang tidak rekursif kiri (termasuk produksi ε): A
β1 | β2 | β3 | ... .. Βm 2. Dari situ kita bisa tentukan α1, α2, .... αn, dan β1, β2, .... βm dari setiap aturan produksi yang memiliki simbol ruas kiri yang sama 3. Lakukan penggantian aturan produksi yang rekursif kiri, menjadi sebagai berikut: 1) A
β1Z | β2Z | .... βmZ 2) Z
α1 | α2 | α3 | .... αn 3) Z
α1Z | α2Z | α3Z | .... αnZ 4. Penggantian diatas dilakukan untuk setiap aturan produksi dengan simbol ruas kiri yang sama. Bisa muncul simbol variabel baru Z1, Z2 dan seterusnya, sesuai banyaknya variabel yang menghasilkan produksi yang rekursif kiri. Hasil akhir berupa aturan produksi pengganti ditambah dengan aturan produksi semula yang tidak rekursif kiri.

Contoh, tata bahasa bebas konteks: S
Sab | aSc |dd | ff | Sbd Pertama-tama kita lakukan pemisahan aturan produksi Aturan produksi yang rekursif kiri: S
Sab | Sbd Dari situ kita tentukan: Untruk simbol ruas kiri S: α1=ab, α2=bd Aturan produksi yang tidak rekursif kiri: S
aSc | dd | ff Dari situ kita dapatkan: Untuk simbol ruas kiri S: β1=aSc, β2=dd, β3=ff Kita lakukan penggantian aturan produksi yang rekursif kiri: Untuk yang memiliki simbol ruas kiri S: S
Sab | Sbd, digantikan oleh: i. S
aScZ1 | dd Z1 | ffZ1 ii. Z1
ab | bd iii. Z1
abZ1 | bd Z1 Hasil akhir setelah penghilangan rekursif kiri adalah: S
aSc | dd | ff S
aScZ1 | dd Z1 | ffZ1 Z1
ab | bd Z1
abZ1 | bd Z1

Contoh lain, terdapat tata bahasa bebas konteks: S
Sab | Sb | cA A
Aa | a | bd Pertama-tama kita lakukan pemisahan aturan produksi Aturan produksi yang rekursif kiri: S
Sab | Sb A
Aa Dari situ kita tentukan: Untuk simbol ruas kiri S: α1= ab, α2 =b Untuk simbol ruas kiri A: α1 = a Aturan produksi yang tidak rekursif kiri: S
cA A
a | bd Dari situ kita dapatkan Untuk simbol ruas kiri S: β1 = cA Untuk simbol ruas kiri A: β1 = a, β2 = bd

Kita lakukan penggantian aturan produksi yang rekursif kiri: Untuk yang memiliki simbol ruas kiri S: S
Sab | Sb, digantikan oleh: i. S
cAZ1 ii. Z1
ab | b iii. Z1
abZ1 | bZ1 Untuk yang memiliki simbol ruas kiri A : A
Aa, digantikan oleh: i. A
a Z2 | bdZ2 ii. Z2
a iii. Z2
a Z2 Hasil akhir setelah penghilangan rekursif kiri adalah: S
cA A
a | bd S
cAZ1 Z1
ab | b Z1
abZ1 | bZ1 A
a Z2 | bdZ2 Z2
a Z2
a Z2 *Perhatikan bahwa penghilangan rekursif kiri memunculkan simbol variabel baru, dan aturan produksi baru yang rekursif kanan.

Contoh lain, terdapat tata bahasa bebas konteks: S
Sa |aAc | c | ε A
Ab | ba Pertama-tama kita lakukan pemisahan aturan produksi Aturan produksi yang rekursif kiri: S
Sa A
Ab Dari situ kita tentukan: Untuk simbol ruas kiri S: α1 = a Untuk simbol ruas kiri A: α1 = b Aturan produksi yang tidak rekursif kiri: S
aAc | c | ε A
ba Dari situ kita dapatkan untuk simbol ruas kiri S:β1 = aAc, β2= c, β3 = ε untuk simbol ruas kiri A: β1 = ba

Perhatikan produksi ε termasuk produksi yang tidak rekursif kiri Kita lakukan penggantian aturan produksi yang rekursif kiri: Untuk yang memilki simbol ruas kiri S: S
Sa, digantikan oleh: i. S
aAcZ1 | cZ1 | Z1 ii. Z1
a iii. Z1
a Z1 Untuk yang memiliki simbol ruas kiri A: A
Ab, digantikan oleh: i. A
ba Z2 ii. Z2
b iii. Z2
bZ2 Hasil akhir setelah penghilangan rekursif kiri adalah: S
aAc | c | ε S
aAcZ1 | cZ1 | Z1 A
ba A
ba Z2 Z1
a Z1
a Z1 Z2
b Z2
b Z2 *

PERTEMUAN 14 14 MESIN TURING

Mesin turing mempunyai 7 Tuple M = (Q, ∑, Γ, δ, S, F, θ) Q

= himpunan state

∑

= Himpunan simbol input

Γ

= simbol pada pita

δ

= fungsi transisi

S

= state awal, S ∈ Q

F

= himpunan state akhir

b

= simbol kosong (blank)

Contoh : Terdapat mesin turing dengan konfigurasi Q = { q1, q2 } ∑ = { a, b } Γ = { a, b, b } F = { q2 }

R = Right

S = { q1 }

L = Left

Fungsi transisi δ ( q1, a)

= (q1, a, R)

δ ( q1, b)

= (q1, a, R)

δ (q1, b )

= (q2, b ,L)

- δ (q1, a) = (q1, a, R) State q1, head menunjuk karakter ‘a’ pada pita menjadi state q1, head bergerak ke kanan. - δ (q1, b) = (q1, a, R) State q1, head menunjuk karakter ‘b’ pada pita menjadi state q1, head menulis karakter ‘a’ lalu bergerak ke kanan - δ ( q1, b ) = (q2, b , L) Pada State q1, head menunjuk karakter ‘ b ’ pada pita menjadi state q2, head bergerak ke kiri.

Jika mesin turing tersebut menerima input ‘abbaa’, apakah diterima oleh mesin turing atau ditolak

1. Pita yang dibaca ‘abbaa’ a b b a a Fungsi transisi δ(q1 ) = (q1, a, R)

State q1

2. a

b

b

a

a

State q1

Fungsi transisi δ (q1, b) = (q1, a, R) Head menulis ‘a’ lalu bergerak ke kanan 3. a

a

b

a

a

State q1

Fungsi transisi δ (q1, b) = (q1, a, R) Head menulis ‘a’ lalu bergerak ke kanan

4. a

a

a

a

a

State q1

Fungsi transisi δ (q1, a) = (q1, a, R) Head bergerak ke kanan 5. a

a

a

a

a

State q1

Fungsi transisi δ (q1, a) = (q1, a, R) Head bergerak ke kanan 6. a

a

a

a

a

b State q1

Fungsi transisi δ (q1, b ) = (q2, b, L) Head menunjuk ‘ b ’ lalu head bergerak ke kiri 7. a

a

a

a

a

b

State q2

State berhenti pada diterima.

q2, q2 adalah final state, maka state input ‘ abbaa’