BAB I

KOMPONEN TATA BAHASA

1.2. Beberapa Pengertian Dasar :

Dalam pembicaraan Grammar, anggota alphabet dinamakan simbol terminal atau token. Kalimat adalah deretan hinggga simbol-simbol terminal. Bahasa adalah himpunan kalimat-kalimat. Anggota bahasa bisa hingga bisa tak hingga kalimat.

Simbol berikut adalah simbol terminal :

-huruf kecil awal alphabet, misal a, b, c

– simbol operator, misal +, -, dan x

-simbol tanda baca, misal (,), dan ;

-string yang tercetak tebal, misal if, then, else

Simbol berikut adalah simbol non terminal :

-huruf besar awal alphabet, misal A, B, C

-huruf S sebagai simbol awal

-string yang tercetak miring, misal expr dan stmt

· 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 e (atau ^) sehingga ïeï= 0. String hampa dapat dipandang sebagai simbol hampa karena keduanya tersusun dari nol buah simbol.

· Alfabet adalah hinpunan hingga (finite set) simbol-simbol.

1.3.Operasi Dasar String

Diberikan dua string : x = abc, dan y = 123

· Prefik string w adalah string yang dihasilkan dari string w dengan menghilangkannol atau lebih simbol-simbol paling belakang dari string w tersebut.

Contoh : abc, ab, a, dan e 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 wtersebut.

Contoh : ab, a, dan e 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 e adalah semua Postfix(x)

· ProperPostfix (atau PoperSufix) string w adalah string yang dihasilkan dari stringw dengan menghilangkan satu atau lebih simbol-simbol paling depan dari string wtersebut.

Contoh : bc, c, dan e 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 simbol-simbol paling belakang dari string w tersebut.

Contoh : abc, ab, bc, a, b, c, dan e 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 simbol-simbol paling belakang dari string w tersebut.

Contoh : ab, bc, a, b, c, dan e 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 e 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 e 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(xy) = x½y = abc atau 123

· Kleene Closure : x* = e½x½xx½xxx½… = e½x½x½x½…

· Positive Closure : x = x½xx½xxx½… = x½x½x½…

1.4. Beberapa Sifat Operasi

· Tidak selalu berlaku : x = Prefix(x)Postfix(x)

· Selalu berlaku : x = Head(x)Tail(x)

· Tidak selalu berlaku : Prefix(x) = Postfix(x) atau Prefix(x) ¹ Postfix(x)

· Selalu berlaku : ProperPrefix(x) ¹ ProperPostfix(x)

· Selalu berlaku : Head(x) ¹ Tail(x)

· Setiap Prefix(x), ProperPrefix(x), Postfix(x), ProperPostfix(x), Head(x), dan Tail(x) adalah Substring(x), tetapi tidak sebaliknya

· Setiap Substring(x) adalah Subsequence(x), tetapi tidak sebaliknya

· Dua sifat aljabar concatenation :

¨ Operasi concatenation bersifat asosiatif : x(yz) = (xy)z

¨ Elemen identitas operasi concatenation adalah e : ex = xe = x

· Tiga sifat aljabar alternation :

¨ Operasi alternation bersifat komutatif : x½y = y½x

¨ Operasi alternation bersifat asosiatif : x½(y½z) = (x½y)½z

¨ Elemen identitas operasi alternation adalah dirinya sendiri : x½x = x

· Sifat distributif concatenation terhadap alternation : x (y½z) = xy½xz

· Beberapa kesamaan :

¨ Kesamaan ke-1 : (x*)* = x*

¨ Kesamaan ke-2 : e½x = x½e = x*

¨ Kesamaan ke-3 : (x½y)* = e½x½y½xx½yy½xy½yx½… = semua string yang merupakan concatenation dari nol atau lebih x, y, atau keduanya.

BAB II

KLASIFIKASI TATA BAHASA FORMAL MENURUT COMSKY

2.1. Fase Analisa

Grammar G didefinisikan sebagai pasangan 4 Tuple : VT, VN, S , Q dan dituliskan sebagai G (VT, VN, S, Q), dimana :

VT : himpunan simbol terminal (atau himpunan token-token, atau alphabet)

VN : himpunan simbol-simbol non terminal

S ϵ VN : simbol awal (atau simbol start)

Q : himpunan produksi

Berdasarkan komposisi bentuk ruas kiri dan kanan produksinya (α → β), Noam Chomsky mengklasifikasikan 4 tipe grammar :

Grammar tipe-0 : UNRESTRICTED GRAMMAR (UG)

Ciri : α, β ϵ (VT | VN)*, | α | > 0

Grmmar tipe-1 : CONTEXT SENSITIVE GRAMMAR (CSG)

Ciri : α, β ϵ (VT | VN)*, 0 < | α | ≤ | β |

Grammar tipe-2 : CONTEXT FREE GRAMMAR (CFG)

Ciri : α ϵ VN , β ϵ (VT | VN)*

Grammar tipe-3 : REGULLAR GRAMMAR (RG)

Ciri : α ϵ VN , β ϵ {VT , VT VN} atau α ϵ VN , β ϵ {VT , VN VT }

Mengingat ketentuan simbol-simbol maka ciri RG sering ditulis sebagai :

α ϵ VN , β ϵ {a , bC} atau α ϵ VN , β ϵ {a , Bc}

Contoh analisa penentuan type grammar

1. Grammar G1 dengan Q1 = {S→aB, B→bB, B→b}.

2. Grammar G2 dengan Q2 = {S→Ba, B→bB, B→b}.

Grammar G1 dengan Q1 = {S→aB, B→bB, B→b}. Ruas kiri semua produksinya terdiri dari sebuah VN maka G1 kemungkinan type CFG atau RG.

Selanjutnya karena semua ruas kanannya terdiri dari sebuah VT atau String VT VN maka G1 adalah RG

Grammar G2 dengan Q2 = {S→Ba, B→bB, B→b}. Ruas kiri semua produksinya terdiri dari sebuah VN maka G2 kemungkinan type CFG atau RG.

Selanjutnya karena semua ruas kanannya mengandung String VT VN (yaitu bB) dan juga String VN VT (Ba) maka G3 bukan RG, dengan kata lain G3 adalah CFG

2.2.Equivalensi 2 AHD

Dua buah AHD dikatakan equivalen jika keduanya dapat menerima bahasa yang sama. Misalkan kedua AHD tersebut adalah A dan A’. Misalkan pula bahasa yang diterima adalah bahasa L yang dibangun oleh alfabet V

= {a1, a2, a3, ..., an}. Berikut ini algoritma untuk menguji equivalensi dua buah AHD.

1. Berikan nama kepada semua stata masing-masing AHD dengan nama berbeda. Misalkan nama-nama tersebut adalah : S, A1, A2, ... untuk AHD A, dan : S’, A1’, A2’, ... untuk AHD A’.

2. Buat tabel (n+1) kolom, yaitu kolom-kolom : (v, v’), (v

, v

’), ..., (v

, v

’), yaitu pasangan terurut (stata AHD A, stata AHD A’).

3. Isikan (S, S’) pada baris pertama kolom (v, v’), dimana S dan S’ masing-masing adalah stata awal masing-masing AHD.

4. Jika terdapat edge dari S ke A1 dengan label a1 dan jika terdapat edge dari S’ ke A1’ juga dengan label a1, isikan pasangan terurut (A1, A1’) sebagai pada baris pertama kolom (v

, v

’). Lakukan hal yang sama untuk kolom-kolom berikutnya.

5. Perhatikan nilai-nilai pasangan terurut pada baris pertama. Jika terdapat nilai pasangan terurut pada kolom (v

, v

’) s/d (v

, v

’) yang tidak sama dengan nilai pasangan terurut (v, v’), tempatkan nilai tersebut pada kolom (v, v’) baris-baris berikutnya. Lakukan hal yang sama seperti yang dilakukan pada langkah (4). Lanjutkan dengan langkah (5).

6. Jika selama proses di atas dihasilkan sebuah nilai pada kolom (v, v’), dengan komponen v merupakan stata penerima sedangkan komponen v’ bukan, atau sebaliknya, maka kedua AHD tersebut tidak ekuivalen. Proses dihentikan.

7. Jika kondisi (6) tidak dipenuhi dan jika tidak ada lagi pasangan terurut baru yang harus ditempatkan pada kolom (v, v’) maka proses dihentikan dan kedua AHD tersebut ekuivalen.

2.3.Mesin Stata Hingga (MSH)

MSH atau FSM (Finite State Machine) adalah sebuah varians automata hingga. MSH sering juga disebut sebagai automata hingga beroutput atau mesin sekuensial. MSH didefinisikan sebagai pasangan 6 tupel F(K, V

, S, Z, f, g) dimana :

K : himpunan hingga stata,

: himpunan hingga simbol input (alfabet)

S Î K : stata awal

Z : himpunan hingga simbol output

f : K ´ V

® K disebut fungsi next state

g : K ´ V

® Z disebut fungsi output

Contoh :

Berikut ini adalah contoh MSH dengan 2 simbol input, 3 stata, dan 3 simbol output :

K = {q0, q1, q2}	fungsi f :		fungsi g :
S = q0	f(q0,a) = q1	f(q0,b) = q2	f(q0,a) = x	f(q0,b) = y
V = {a, b}	f(q1,a) = q2	f(q1,b) = q1	f(q1,a) = x	f(q1,b) = z
Z = {x, y, z}	f(q2,a) = q0	f(q2,b) = q1	f(q2,a) = z	f(q2,b) = y

MSH dapat disajikan dalam bentuk tabel atau graf. Untuk MSH contoh di atas tabel dan grafnya masing-masing adalah :

a x b z

	a	b	q0 q1
q0	q1, x	q2, y	b x y a
q1	q2, x	q1, z	a b
q2	q0, z	q1, y	q2

y x

Jika MSH di atas mendapat untai masukan “aaba” maka akan dihasilkan :

- untai keluaran : xxyx

- untai stata : q0 q1 q2 q1 q2

2.4.MSH penjumlah biner

MSH dapat disajikan sebagai penjumlah biner. Sifat penjumlahan biner bergantung pada statusnya : carry atau not carry.

Pada status not carry berlaku : 0 + 0 = 0, 1 + 0 = 0 + 1 = 1, 1 + 1 = 0

Pada status carry berlaku : 0 + 0 = 1, 1 + 0 = 0 + 1 = 0, 1 + 1 = 1

Pada status not carry blank (b) menjadi b, sedangkan pada status carry menjadi 1.

Nilai setiap tupel untuk MSH ini adalah :

K = N (not carry), C (carry), dan S (stop)	Tabel MSH
S = N		00	01	10	11	b
V = {00, 01, 10, 11, b}	N	N, 0	N, 1	N, 1	C, 0	S, b
Z = {0, 1, b}	C	N, 1	C, 0	C, 0	C, 1	S, 1

Graf MSH penjumlah biner :

00 0 1 00 01 0

1 10

N 11 0 C

01 0

1 10 1 11

b b

b 1

Contoh :

Hitunglah : 1101011 + 0111011

Jawab :

Input = pasangan digit kedua bilangan, mulai dari LSB (least significant bit)

= 11, 11, 00, 11, 01, 11, 11, b

Output = 0, 1, 1, 0, 0, 1, 1, 1 (jawab : dibaca dari kanan)

Stata = N, C, C, N, C, C, C, C, S

Periksa : 1 1 0 1 0 1 1

0 1 1 1 0 1 1 +

1 1 1 0 0 1 1 0

2.5.Ekspresi Regula

Bahasa regular dapat dinyatakan sebagai ekspresi regular dengan menggunakan 3 operator : concate, alternate, dan closure. Dua buah ekspresi regular adalah ekuivalen jika keduanya menyatakan bahasa yang sama

Contoh :

= {a

½ n ³ 1, m ³ 1} Û er

= a

b a

= {a

½ n ³ 0, m ³ 0} Û er

= a* b a*

Perhatikan bahwa kita tidak bisa membuat ekspresi regular dari bahasa

= {a

½ n ³ 1} atau L

= {a

½ n ³ 0}, karena keduanya tidak dihasilkan dari grammar regular.

Kesamaan 2 ekspresi regular :

(a b)* a = a (b a)*

Bukti :

(a b)* a = (eï(ab)ï(abab)ï…) a = (e aï(aba)ï(ababa)ï…) = (aï(aba)ï(ababa)ï…)

= a (eï(ba)ï(baba)ï…) = a (b a)*

Latihan 2. Buktikan kesamaan ekspresi regular berikut :

1. (a*ïb)* = (aïb)*

2. (aïb*)* = (aïb)*

3. (a* b)* a* = a* (b a*)*

4. (a a*)(eïa) = a*

5. a(b aïa)* b = a a* b(a a* b)*

BAB III

AUTMA HINGGA NON DETERMINISTIK DAN PENGANTAR TRANSLATOR

3.1. AH Determinstik (AHD)

Automata Hingga Deterministik atau AHD tidak bisa mengubah stata tanpa membaca sebuah karakter masukan dan AHD bersifat rekursif, yang menunjukkan di stata mana AHD berada pada saat di mulai di stata q dengan mendapat input berupa string w = tT. String w diterima oleh AHD jika setelah membaca habis semua karakter dari untai, AHD berada pada sebuah Stata Akhir.

Fungsi Transisi akibat pembacaan sebuah simbol bersifat tertentu, artinya

- Setiap cell hanya terdapat satu (1) digit stata tujuan

- Setiap stata terdapat busur panah keluar sebanyak input yang ada

Berikut ini sebuah contoh AHD F(Q, V T , σ, q0, Z), dimana :

Q = {q0, q1, q2} σ diberikan dalam tabel berikut :

Ilustrasi graf untuk AHD F adalah sebagai berikut :

Lambang stata awal adalah node dengan anak panah.

Lambang stata awal adalah node ganda.

Gambar1. Tabel AHD

Contoh kalimat yang diterima AHD : a, b, aa, ab, ba, aba, bab, abab, baba

Contoh kalimat yang tidak diterima AHD : bb, abb, abba

AHD ini menerima semua kalimat yang tersusun dari simbol a dan b yang tidak mengandung substring bb. sebuah kalimat diterima oleh AHD jika tracingnya berakhir di salah satu stata penerima.

3.2.AH Non Determinstik (AHN)

AHN atau bisa dibilang Automata Hingga Nondeterministik pada hakekatnya adalah sama seperti AHD, hanya saja pada AHN dimungkinkan adanya transisi dari suatu stata ke lebih dari satu stata, untuk sebuah karakter input yang sama. Sebuah untai akan diterima AHN, jika sedikitnya satu urutan transisi state berakhir pada Stata Akhir.

Fungsi Transisi akibat pembacaan sebuah simbol bersifat tertentu, artinya

- Setiap cell dapat berisi nol, satu bahkan lebih dari satu digit

- Setiap stata boleh terdapat busur panah dengan input yang sama, namun tujuan yang berbeda.

Berikut ini sebuah contoh AHN F(Q, V T , σ, q0, Z), dimana :

Q = {q 0 , q1, q 2 ,q 3 , q 4 } σ diberikan dalam tabel berikut :

Ilustrasi graf untuk AHN F adalah sebagai berikut :

Contoh kalimat yang diterima AHN di atas : aa, bb, cc, aaa, abb, bcc, cbb

Contoh kalimat yang tidak diterima AHN di atas : a, b, c, ab, ba, ac, bc

Fungsi transisi σ sebuah AHN dapat diperluas sebagai berikut :

1. σ (q, ε) = {q} untuk setiap q ∈ Q

2. σ (q, t T) = ∪ σ (p i , T) dimana t ∈ V T , T adalah V T *, dan σ (q, t) = {p i }

3. σ ({q1, q2, …, qn}, x) = ∪ σ (q i ,x), untuk x ∈ V T *

Sebuah kalimat di terima AHN jika salah satu tracing-nya berakhir di stata penerima, atau himpunan stata setelah membaca string tersebut mengandung stata penerima.

Dan jika dilihat dari isi tabelnya, jelas terlihat perbedaan dari AHD dan AHN. Berikut datailnya :

3.3.Equivalensi Ahn Menjadi AHD

Bentuk Otomata Nondeterministik dapat diubah menjadi bentuk Deterministik tanpa mengubah arti.

Berikut Algoritmanya :

1. Tetapkan Stata awal AHD = Stata awal AHN atau selanjutnya ditulis S(AHD) = S(AHN)

2. Tetapkan Input AHD = Input AHN atau selanjutnya ditulis V(AHD) = V(AHN)

3. Copykan tabel AHN sebagai tabel AHD, mula-mula Stata AHD = Stata AHN atau selanjutnya ditulis K(AHD) = K(AHN) dan Fungsi transisi AHD = Fungsi transisi AHN atau selanjutnya ditulis M(AHD) = M(AHN)

4. Setiap stata yang merupakan nilai dari fungsi M(AHN) namun stata tersebut bukan elemen dari K(AHN), maka tetapkanlah sebagai elemen baru dari K(AHD). Tempatkan stata tersebut pada kolom stata M(AHD). Lakukan pemetaan sesuai berdasarkan fungsi M(AHN).

5. Ulangi langkah 4 hingga tidak diperoleh stata baru.

6. Stata Penerima AHD atau selanjutnya ditulis Z(AHD) adalah semua stata yang mengandung stata elemen Z(AHN).

Contoh Soal :

Buatlah AHD yang equivalen dengan AHN berikut :

Jawab :

1. S(AHN) = S(AHD) = A

2. V(AHN) = V(AHD) = {0,1}

3. Copykan tabel AHN

4. Simbol - dianggap sebagai elemen baru, kemudian petakan berdasarkan fungsi M(AHN).

5. 5 karena tidak ada pengulangan makan lanjutkan ke langkah berikutnya.

6. Z(AHD) = Z(AHN) = {B} karena tidak ada lagi elemen baru yang mengandung elemen Z(AHN). Dan hasilnya adalah :

3.4.Automata Hingga Non Deterministik Dengan Transisi e (e-Move)

Ekivalen AHN dengan e-move ke AHN tanpa e-move

Diketahui AHN e-move

e a

Gambarkan AHN tanpa e-move yang ekivalen dengan AHN diatas !

Jawab :

Algoritma :

1. Buat tabel transisi AHN e-move

d	a	b
q0	f	f
q1	{q2}	{q3}
q2	f	f
q3	f	f

2. Tentukan e-closure untuk setiap stata

e-closure(q0) = {q0, q1}

e-closure(q1) = {q1}

e-closure(q2) = {q2}

e-closure(q3) = {q3}

3. Carilah setiap fungsi transisi hasil perubahan dari

AHN e-move ka AHN tanpa e-move

d’(stata, input) = e-closure(d(e-closure(stata), input))

Untuk stata q1 dengan input a, fungsi transisinya adalah

d’(q0, a) = e-closure(d(e-closure(q0),a))

= e-closure(d{q0,q1}, a)

= e-closure{q2}

= q2

…..dan seterusnya sampai stata q2 dengan input f

4. Berdasarkan hasil langkah ke-3 maka dibuat tabel transisisi dan diagram transisi dari AHN tanpa e-move yang ekivalen dengan AHN e-move

d	a	b
q0	{q2}	{q3}
q1	{q2}	{q3}
q2	f	f
q3	f	f

5. Stata akhir atau stata penerima untuk AHN tanpa e-move adalah

F’ = FÈ{q | (e-closure(q)ÇF ≠ f}

Contoh :

Jika F (stata penerima AHN dengan e-move) = {q3}

e-closure(q3) = {q3}

Maka (e-closure(q)ÇF adalah {q3}Çq3 ≠ f = (q3}

Jadi F’ (stata penerima untuk AHN tanpa e-move) adalah F È {q3}= {q3}È{q3}= {q3}

3.5.Automata Hingga Nondeterministik (AHN)

Berikut ini sebuah contoh AHN F(K, V

, M, S, Z), dimana :

K = {q

, q

} M diberikan dalam tabel berikut :

V = {a, b,c}		a	b	c
S = q	q	{q, q}	{q, q}	{q, q}
Z = {q}	q	{q, q}	{q}	{q}
	q	{q}	{q, q}	{q}
	q	{q}	{q}	{q, q}
	q	Æ	Æ	Æ

Ilustrasi graf untuk AHN F adalah sebagai berikut :

a, b, c a, b, c

c b a

a, b, c a, b, c

Contoh kalimat yang diterima AHN di atas : aa, bb, cc, aaa, abb, bcc, cbb

Contoh kalimat yang tidak diterima AHN di atas : a, b, c, ab, ba, ac, bc

Fungsi transisi M sebuah AHN dapat diperluas sebagai berikut :

1. M(q, e) = {q} untuk setiap q Î K

2. M(q, t T) = È M(p

, T) dimana t Î V

, T adalah V

*, dan M(q, t) = {p

}

3. M({q

, q

, …, q

}, x) = È M(q

,x), untuk x Î V

Sebuah kalimat di terima AHN jika :

· salah satu tracing-nya berakhir di stata penerima, atau

· himpunan stata setelah membaca string tersebut mengandung stata penerima

Contoh :

Telusurilah, apakah kalimat-kalimat berikut diterima AHN : ab, abc, aabc, aabb

Jawab :

i) M(q

,ab) Þ M(q

,b) È M(q

,b) Þ {q

, q

} È {q

} = {q

, q

}

Himpunan stata tidak mengandung stata penerima Þ kalimat ab tidak diterima

ii) M(q

,abc) Þ M(q

,bc) È M(q

,bc) Þ {M(q

,c) È M(q

,c)} È M(q

, c)

Þ {{ q

, q

}È{ q

}}È{ q

} = {q

, q

}

Himpunan stata tidak mengandung stata penerima Þ kalimat abc tidak diterima

iii) M(q

,aabc) Þ M(q

,abc) È M(q

,abc) Þ {M(q

,bc) È M(q

,bc)} È M(q

,bc)

Þ {{M(q

, c) È M(q

,c)} È M(q

, c)} È M(q

, c)

Þ {{{ q

, q

}È { q

}} È {q

} = {q

, q

}

Himpunan stata tidak mengandung stata penerima Þ kalimat aabc tidak diterima

iv) M(q

,aabb) Þ M(q

,abb) È M(q

,abb) Þ {M(q

,bb) È M(q

,bb)} È M(q

,bb)

Þ {{M(q

, b) È M(q

,b)} È M(q

, b)} È M(q

, b)

Þ {{{ q

, q

}È { q

, q

}} È {q

} = {q

, q

}

Himpunan stata tidak mengandung stata penerima Þ kalimat aabb diterima

AHN Dengan Transisi Hampa

Perhatikan AHN berikut.

1 0

q q

AHN di atas mengandung ruas dengan bobot e. AHN demikian dinamakan AHN dengan transisi e, atau singkatnya AHN-e. AHN-e di atas menerima bahasa L = {1

½i , j ³ 0}

3.6.Ekuivalensi AHN, AHD, dan GR

AHD bisa dibentuk dari AHN. AHN

GR bisa dibentuk dari AHD.

AHN bisa dibentuk dari GR. AHD GR

Pembentukan AHD dari AHN

Diberikan sebuah AHN F = (K, V

, M, S, Z). Akan dibentuk sebuah AHD F’ = (K’, V

’, M’, S’, Z’) dari AHN F tersebut. Algoritma pembentukannya adalah sbb. :

1. Tetapkan : S’ = S dan V

’ = V

2. Copykan tabel AHN F sebagai tabel AHD F’. Mula-mula K’ = K dan M’ = M

3. Setiap stata q yang merupakan nilai (atau peta) dari fungsi M dan q Ï K, ditetapkan sebagai elemen baru dari K’. Tempatkan q tersebut pada kolom Stata M’, lakukan pemetaan berdasarkan fungsi M.

4. Ulangi langkah (3) sampai tidak diperoleh stata baru.

5. Elemen Z’ adalah semua stata yang mengandung stata elemen Z.

Contoh :

Berikut ini diberikan sebuah AHN F = (K, V

, M, S, Z) dengan :

K = {A, B, C}, V

= {a, b}, S = A, Z = {C}, dan M didefinisikan sebagai berikut :

Stata K	Input
AHN F	a	b
A	[A,B]	C
B	A	B
C	B	[A,B]

Tentukan AHD hasil transformasinya.

Jawab :

Berdasarkan algoritma di atas, maka :

1. S’ = S = A, V

’ = V

= {a, b}.

2. Hasil copy tabel AHN F menghasilkan tabel AHD F’ berikut :

Stata K’	Input
AHD F’	a	b
A	[A,B]	C
B	A	B
C	B	[A,B]

3. Pada tabel AHD F’ di atas terdapat stata baru yaitu [A,B]. Pemetaan [A,B] adalah : M([A,B],a) = M(A,a) È M(B,a) = [A,B] È A = [A,B], dan

M([A,B],b) = M(A,b) È M(B,b) = C È B = [B,C], sehingga diperoleh tabel berikut :

Stata K’	Input
dari AHD F’	a	b
A	[A,B]	C
B	A	B
C	B	[A,B]
[A,B]	[A,B]	[B,C]

4. Langkah (3) di atas menghasilkan stata baru yaitu [B,C]. Setelah pemetaan terhadap [B,C] diperoleh tabel berikut :

Stata K’	Input
dari AHD F’	a	b
A	[A,B]	C
B	A	B
C	B	[A,B]
[A,B]	[A,B]	[B,C]
[B,C]	[A,B]	[A,B]

5. Setelah langkah (4) di atas tidak terdapat lagi stata baru.

Dengan demikian AHD F’ yang dihasilkan adalah : AHD F’ = (K’, V

’, M’, S’, Z’), dimana : K’ = {A, B, C, [A,B], [B,C]}, V

’ = {a, b}, S’ = A, Z’ = {C, [B,C]}. Fungsi transisi M’ serta graf dari AHD F’ adalah sebagai berikut :

B b

Stata K’	Input		a
dari AHD F’	a	b	A a
A	[A,B]	C	a b C
B	A	B
C	B	[A,B]	b
[A,B]	[A,B]	[B,C]	[A,B] b [B,C]
[B,C]	[A,B]	[A,B]	a, b

Pembentukan GR dari AHD

Diketahui sebuah AHD F = (K, V

, M, S, Z). Akan dibentuk GR G = (V

’,V

, S’, Q).

Algoritma pembentukan GR dari AHD adalah sebagai berikut :

1. Tetapkan V

’ = V

, S’ = S, V

= S

2. Jika A

, A

Î K dan a Î V

, maka :

M(A

, a) = A

ekuivalen dengan produksi :

Contoh

Diketahui sebuah AHD F dengan Z = {S} dan fungsi transisi M sebagai berikut :

Stata K	Input		Dengan algoritma di atas maka diperoleh Q(GR) sbb. :
AHD F	0	1	M(S,0) = B Û S ® 0B	M(S,1) = AÛ S ® 1A
S	B	A	M(A,0) = C Û A ® 0C		M(A,1) = SÛ A ® 1
A	C	S	M(B,0) = S Û B ® 0		M(B,1) = CÛ B® 1C
B	S	C	M(C,0) = A Û C ® 0A		M(C,1) = BÛ C ® 1B
C	A	B

GR yang dihasilkan adalah G(V

’,V

, S’, Q), dengan V

’ = {0,1}, V

= {S, A, B, C}, S’ = S, dan Q = {S ® 0B, S ® 1A, A ® 0C, B® 1C, C ® 0A, C ® 1B, A ® 1, B ® 0}

Pembentukan AHN dari GR

Diketahui GR G = (V

, S, Q). Akan dibentuk AHN F = (K,V

’, M, S’, Z).

Algoritma pembentukan AHN dari GR :

1. Tetapkan V

’ = V

, S’ = S, K = V

2. Produksi A

® a A

ekuivalen dengan M(A

, a) = A

Produksi A

® a ekuivalen dengan M(A

, a) = X, dimana X Ï V

3. K = K È {X}

4. Z = {X}

Contoh

Diketahui GR G = (V

, S, Q) dengan : V

= {a, b}, V

= {S, A, B}, S = S, dan

Q = {S ® aS, S ® bA, A ® aA, A ® aB, B ® b}

Terapkan algoritma di atas untuk memperoleh AHN F sebagai berikut :

1. V’ = V = {a, b}, S’ = S, K = V = {S, A, B}	Tabel M :
2. S ® aS Û M(S,a) = S, S ® bA Û M(S,b) = A,	Stata K	Input
A ® aA Û M(A,a) = A, A ® aB Û M(A,a) = B,	AHN F	a	b
B ® b Û M(B,b) = X	S	S	A
AHN yang diperoleh : F(K,V’, M, S’, Z), dengan	A	[A,B]	f
K = {S, A, B, X}, V’ = {a, b}, S’ = S, Z = {X},	B	f	X
	X	f	f

IV.8. Ekuivalensi Ahn-e Dengan ER (Ekspresi Regular)

Jenis ER	Simbol ER	AHN
Simbol hampa	e	q
ER hampa	f atau {}	q q
ER umum	r	r q q
Alternation	r\| r	e r e q e e q r
Concatenation	rr	e e e q r r q
Kleene Clossure	r *	e e e q r q e

Contoh :

Tentukan AHN untuk ekspresi regular r = 0(1 | 23)*

Jawab :

= 0 Û q

= 1 Û q

2 3

= 23 Û q

e e

= r

| r

= 1| 23 Û q

e e

2 3

e e e e

= r

* = (1| 23)* Û q

e 2 3 e

0 e e e e

r = r

= 0(1| 23)* Û q

e 2 3 e

BAB IV

AUTOMATA PUSHDOWN ATAU APD

4.1. Tata Bahasa Konteks

Tata bahasa bebas konteks ini merupakan notasi penting yang digunakan untuk mendeskripsikan sruktur bahasa pemograman dan himpunan-himpunan untai yang berhubungan; digunakan untuk membuat komponen parser pada compiler.

4.2.Mesin Turing

Mesin turing adalah otomata yang menjadi model computer yang kita kenal saat ini. Mesin turing memungkinkan kita untuk mempelajari decidability, yaitu pertanyaan mengenai apa yang dapat dan tidak dapat dikerjakan oleh computer. mesin ini juga memungkinkan kita menbedakan tractable problem (dapat dipecahkan dalam waktu polynomial) dari intractable problem (tidak dapat dipecahkan dalam waktu polynomial).

Sunday, April 22, 2018

Makalah Automata

Himpunan stata tidak mengandung stata penerima Þ kalimat ab tidak diterima

AHN Dengan Transisi Hampa

q q

Pembentukan AHD dari AHN

Pembentukan GR dari AHD

Pembentukan AHN dari GR

No comments:

Post a Comment