Teknik Kompilasi – Jarak Titik dan Lingkaran

Pseudocode dan Code Generator pada post kali ini untuk:

input titik pusat dari lingkaran beserta dengan jari-jarinya, input titik lain, lalu program akan mencari apakah titik lain tersebut terletak di luar, di dalam atau persis di titik jari-jari lingkaran.

Pseudocode:
float distance, distanceX, distanceY;
input Xa, Ya, Ra;
input Xb, Yb;
distanceX = Xa-Xb;
distanceY = Ya-Yb;
distance = sqrt(pow(distanceX,2) + pow(distanceY,2));
if(distance > Ra)
print ‘diluar lingkaran’;
else if (distance == Ra)
print ‘sama dengan jari-jari’;
else print ‘di dalam lingkaran’

Code Generator
Representatif Machine Language:
01. mov Xa, R0
02. mov Xb, R1
03. sub R1, R0
04. mov R0, distanceX
05. mov Ya, R2
06. mov Yb, R3
07. sub R3, R2
08. mov R2, distanceY
09. mov distanceX, R4
10. pow #2, R4
11. mov distanceY, R5
12. pow #2, R5
13. add R5, R4
14. sqrt #2, R4
15. mov Ra, R6
16. gt R6, R4
17. jmpF R4, (20)
18. prt , “diluar lingkaran”
19. jmp ,(25)
20. eq R6, R4
21. jmpF R4, (24)
22. prt , “sama dengan jari-jari”
23. jmp , (25)
24. prt , “di dalam lingkaran”
25. …

 

www.binus.ac.id

  • Digg
  • Del.icio.us
  • StumbleUpon
  • Reddit
  • Twitter
  • RSS

Tugas Teknik Kompilasi

  1. S -> S+A | S-A  | A+S | A-S | B*A

B-> aB | B(a+B) | B*a | a(a+B) | b

A-> a

Tentukan First, Follow dan Table dari Production diatas!

Jawaban:

–          Left Recursive

S-> A+SS’ | A-SS’ | B*AS’

S’-> +AS’ | -AS’ | e

B-> aBB’ | a(a+B)B’ | bB’

B’-> (a+B)B’ | *aB’ | e

A->a

–          Left Factory

S-> AS”  | B*AS’

S’-> +AS’ | -AS’ | e

S”-> +SS’ | -SS’

B-> aB” | bB’

B’-> (a+B)B’ | *aB’ | e

B”-> BB’ | (a+B)B’

A->a

First (S) = {a, b}

First (S’) = {+, -, e}

First (S”) = {+, -}

First (B) = {a, b}

First (B’) = {(, *, e}

First (B”) = {a, b, (}

First (A) = {a}

Follow (S) = {$, +, -}

Follow (S’) = {$, +, -}

Follow (S”) = {$, +, -}

Follow (B) = {), (, *}

Follow (B’) = {), (, *}

Follow (B”) = {), (, *}

Follow (A) = {$, +, -}

a

b

(

)

+

*

$

S

S-> AS’’ | B*AS’

S-> B*AS

S’

S’-> +AS’ | e

S’-> -AS’ | e

S’->e

S’’

S’’-> +SS’

S’’-> -SS’

B

B-> aB”

B-> bB’

B’

B’-> (a+B)B’ | e

B’->e

B’-> *aB’ | e

B’’

B”-> BB’

B”-> BB’

B”-> (a+B)B’

A

A->a

2.

S->if E the S|if E then S else S|v:=E

V->id|id[E]

E->E+T|E-T|T

T->T*F|T/F|F

F->V|(E)|const

Jawab:

S->if E then S S’ | V:=E

S’-> ε |else S

V->id V’

V’-> ε | [E]

E->T E’

E’-> +TE’ | -TE’| ε

T’->FT’

T’-> *FT’|/FT’| ε

F->V|(E)|const

First (S)= {if , id}

First (S’)= {ε , else}

First (V)= {id}

First (V’)= {ε , [ }

First (E)= {id, ( , const}

First (E’)= {+, -, ε}

First (T)= {id, (, const}

First (T’)= {* , / , ε}

First (F)={id, (, const}

Follow (S)={ $ , else }

Follow (S’)= { $ , else }

Follow (V)= { : , * , / }

Follow (V’)= {  [ , : , * , / }

Follow (E)= { then, $ , else }

Follow (E’)= { then, $ , else }

Follow (T)= { + , – }

Follow (T’)= { + , – }

Follow (F)= { * , / }

Untitled

3. Soal :

S ->  a = A

A -> aA’ | bA’

A’ -> +AA’ | e

First :

First (S) = { a }

First (A) = {a , b}

First (A’) = {+ , e }

Follow :

Follow (S) = { $ }

Follow (A) = { $ , +}

Follow (A’) = { $ , + }

Table :

$

+

a

b

S

S ->  a = A

A

A -> aA’ | bA’ A -> aA’ | bA’

A’

A’ -> e

A’ -> +AA’

A’ ->e

4. Diketahui grammar :

be ->bt be’

be’ ->or bt be’

be’ ->e

bt ->bf bt’

bt’ ->and bf bt’

bt’ ->e

bf ->not bf

bf ->( be)

bf ->true

bf ->false

Periksalah input sebagai berikut : not (true or false) and true and true and false not (false) true

Menentukan First

First (be)              : not, (, true, false

First (be’)            : or, e

First (bt)               : not, (, true, false

First (bt’)             : e, and

First (bf)               : not, (, true, false

Menentukan follow

Follow (be)         : { $, ) }

Follow (be’)        : { $, ) }

Follow (bt)          : { or, $, ) }

Follow (bt’)         : { or, $, ) }

Follow (bf)          : { or, $, ), and }

Tabel

not true false
  • or
and ( ) $
be be ->bt be’ be ->bt be’ be ->bt be’ be ->bt be’
be’ be’ ->or bt be’
bt bt ->bf bt’ bt ->bf bt’ bt ->bf bt’
bt’ bt’ ->e bt’ ->and bf bt’
bf bf ->not bf bf àtrue bf àfalse

Pemeriksaan Input

No. Stack Input Output
1. be $ not (true or false) and true and true and false not (false) true $ be ->bt be’
2. bt be’ $ not (true or false) and true and true and false not (false) true$ bt ->bf bt’
3. bf bt’ be’ $ not (true or false) and true and true and false not (false) true$ bf ànot bf
4. notbfbt’ be’ $ not (true or false) and true and true and false not (false) true$ pop not
5. bf bt’ be’ $ (true or false) and true and true and false not (false) true$ bf ->(be)
6. (be) bt’ be’ $ (true or false) and true and true and false not (false) true$ pop (
7. be) bt’ be’ $ true or false) and true and true and false not (false) true$ be àbt be’
8. bt be’) bt’ be’ $ true or false) and true and true and false not (false) true$ bt ->bf bt’
9. bf bt’ be’) bt’ be’ $ true or false) and true and true and false not (false) true$ bf ->true
10. truebt’ be’) bt’ be’ $ true or false) and true and true and false not (false) true$ pop true
11 bt’ be’) bt’ be’ $ or false) and true and true and false not (false) true$ bt’ ->ε
12 be’) bt’ be’ $ or false) and true and true and false not (false) true$ be’ àor bt be’
13. orbt be’ ) bt’ be’ $ or false) and true and true and false not (false) true$ pop or
14. bt be’) bt’ be’ $ false) and true and true and false not (false) true$ bt ->bf bt’
15. bf bt’ be’) bt’ be’ $ false) and true and true and false not (false) true$ bf ->false
16. falsebt’ be’) bt’ be’ $ false) and true and true and false not (false) true$ pop false
17. bt’ be’) bt’ be’ $ ) and true and true and false not (false) true$ bt’ ->ε
18. be’) bt’ be’ $ ) and true and true and false not (false) true$ be’ ->ε
19. )bt’ be’ $ ) and true and true and false not (false) true$ pop )
20. bt’ be’ $ and true and true and false not (false) true$ bt’ ->and bf bt’
21. and bf bt’ be’ $ and true and true and false not (false) true$ pop and
22. bf bt’ be’ $ true and true and false not (false) true$ bf ->true
23. truebt’ be’ $ true and true and false not (false) true$ pop true
24. bt’ be’ $ and true and false not (false) true$ bt’ ->and bf bt’
25. and bf bt’ be’ $ and true and false not (false) true$ pop and
26. bf bt’ be’ $ true and false not (false) true$ bf ->true
27. truebt’ be’ $ true and false not (false) true$ pop true
28. bt’ be’ $ and false not (false) true$ bt’ ->and bf bt’
29. and bf bt’ be’ $ and false not (false) true$ pop and
30. bf bt’ be’ $ false not (false) true$ bf ->false
31. falsebt’ be’ $ false not (false) true$ pop false
32. bt’ be’ $ not (false) true$ ditolak

www.binus.ac.id

  • Digg
  • Del.icio.us
  • StumbleUpon
  • Reddit
  • Twitter
  • RSS

Tugas GSLC-1 Metode Numerik

SOAL  TUGAS   GSLC 1- METODE NUMERIK

Angela Muliawan

1501167380/06PFT

1.     Perusahaan tambang yang sedang melakukan eksplorasi melakukan penelitian kandungan emas disuatu tempat. Berdasarkan hasil penelitian, kandungan emas mengikuti jalur lintasan y=f(x) = ex  . Menurut data satelit, untuk mendapatkan kandungan emas terbanyak ada di posisi x=0.4. Jika posisi pengeboran tersebut dihitung menggunakan pendekatan deret Taylor sampai dengan 4 suku pertama, hitunglah ( pembulatan 4 angka dibelakang koma),Hitunglah :

a. Nilai f(0.5) untuk fungsi f(x) = ex

b. Galat mutlak dan relatifnya.a  Nilai  e   = 2,7183

Jawab :

  1. F ( 0,5) = ex

1

Jadi, f(0,5)  =1,6484

  1. Galat mutlak dan relatifnya

2

SPT = 0,00001 (Untuk 4 angka dibelakang koma)

3 4

Maka, Galat Mutlaknya adalah 0,00005 dan Galat Relatifnya adalah 0,0034

2.   Seorang pembuat boneka ingin membuat dua macam boneka yaitu boneka A dan boneka B. Kedua boneka tersebut dibuat dengan menggunakan dua macam bahan yaitu potongan kain dan kancing. Boneka A membutuhkan 10 potongan kain dan 6 kancing, sedangkan boneka B membutuhkan 8 potongan kain dan 8 kancing. Permasalahannya adalah berapa buah boneka A dan boneka B yang dapat dibuat dari 82 potongan kain dan 62 kancing ? Selesaikan dengan metode gauss-Jourdan !

Jawab :56

Jadi, yang dapat dibuat dari kain dan kancing tersebut adalah 5 buah boneka A dan 4 buah boneka B.

3. Carilah nilai  x1, x2 dan xdari sistem persamaan linear berikut dengan menggunakan metode  dekomposisi LU.7

Jawab :8

Dari persamaan diatas maka didapat :

–          U11 = 1

–          U12 = -3

–          U13 = 1

–          L21. U11 = 3

L21 = 3

–          L21. U12 + U22 = -4

U22 = 5

–          L21.U13 + U23 = 2

U23 = -1

–          L31.U11 = 2

L31 = 2

–          L31.U12 + L32.U32 = -5

2.(-3) + L32.5 = -5

L32 = 0,2

–          1 = L31.U13 + L32.U23 + U33

1 = (2.1) + (-0,2) + U33

U33 = -0,8

Hitung Untuk L.y = b

 

–          y1 = 8

–          3y1 + y2 = 16

y2 = -8

–          2y1 + 0,2y2 + y3 = 12

16 – 1,6 + y3 = 12

y3 = -2,4

Hitung U.x = y

r2

–          (-0,8)x3 = -2,4

x3 = 3

–          5x2 – x3 = -8

5x2 -3 = -8

x2 = -1

–          x1 – 3x2 + x3 = 8

x1 + 3 + 3 = 8

x1 = 2

Maka nilai dari x1, x2 dan x3 nya adalah 2, -1, 3

www.binus.ac.id

  • Digg
  • Del.icio.us
  • StumbleUpon
  • Reddit
  • Twitter
  • RSS

Analisis Entity Relationship Diagram Untuk Twitter

ERD

Penjelasan dari Entity Relationship Diagram

Dalam analisis kami, fitur twiter yang kami fokuskan adalah Follow, Tweet Activity (Membuat tweet baru, retweet dan membalas tweet) serta pesan (mengirim dan menerima pesan).

Data pengguna twitter akan disimpan dalam table MsUser, dimana primary key nya adalah UserID, sedangkan UserName dan Email dibuat unique. Kami tidak membuat UserName sebagai Primary Key supaya lebih memudahkan dalam proses update atau delete tabel lain meskipun username sering diubah oleh pengguna. UserStatus untuk mengetahui apakah user ingin tweetnya bersifat public atau private. Bila bersifat public, semua user dapat melihat tweet dari user tersebut. Sementara bila bersifat private, tweet dari user tersebut hanya dapat dilihat oleh user yang menfollow.

Dalam table TrFollowUser terdapat transaksi follow maupun block, tergantung dari kolom Status.  Table ini akan memetakan Setiap UserID yang difollow (FollowedID) dan UserID yang men-follow (FollowerID).

Table TrTweet akan menyimpan tweet, dimana link akan disimpan dalam kolom Link (Untuk tweet berupa URL ataupun gambar, dapat berisi NULL) dan Content yang akan berisi text. ReferencesTweet akan menyimpan TweetID lain, jika tweet tersebut merupakan hasil retweet atau mereply suatu tweet. Jika tweet yang di post adalah tweet baru maka ReferencesTweetnya adalah kosong (NULL).

Table TrDirectMessage berisi transaksi kirim-mengirim pesan.

Secara keseluruhan setiap tabel mengandung kolom AuditedActivity, AuditedTime dan AuditedUser. AuditedActivity berisi status dari baris tersebut, apakah sudah terhapus, terupdate atau baru terinsert. AuditedTime menyimpan waktu terakhir dari insert, update atau delete baris tersebut sedangkan AuditedUser untuk menyimpan ID dari user yang terakhir mengubah baris tersebut.

 

www.binus.ac.id

  • Digg
  • Del.icio.us
  • StumbleUpon
  • Reddit
  • Twitter
  • RSS

Create & Select Table Menggunakan Keyword SQL

Pada SQL Server, keyword – keyword seperti SELECT, UPDATE, DELETE, INSERT dll sudah di reserved untuk melakukan aksi tertentu. Pertanyaannya adalah, bagaimana bila table atau database yang kita inginkan menggunakan reserved keyword tersebut.
Dalam post kali ini, saya mencontohkan penggunaan keyword UPDATE menjadi nama tabel/entity dan menjadi nama kolom sebuah tabel.

create_error

Create Table Error

create_column_errorCreate Column Error

select_all_errorSelect Error

Berdasarkan percobaan diatas, penggunaan keyword seperti UPDATE dianggap sebagai syntax error. Untuk solusinya, dalam SQL Server dapat menggunakan [] sebagai tanda bahwa kata tersebut bukan sebagai keyword.

create_successCreate Table Success

create_column_successCreate Column Success

select_successSelect Success

www.binus.ac.id

  • Digg
  • Del.icio.us
  • StumbleUpon
  • Reddit
  • Twitter
  • RSS

Web Database Environment

Web Database Environment

–          Data dan Informasi

Data adalah berbagai macam fakta, real atau tidak, dan bersifat kompleks. Data dapat diteliti dan diolah sehingga menghasilkan informasi. Data dapat bersifat public dan private. Contoh data private misalnya adalah data perbankan. Contoh data public misalnya data diri yang kita cantumkan pada profile facebook.

Informasi adalah kombinasi dari fakta-fakta yang telah diolah dan berguna untuk suatu kebutuhan tertentu. Misalnya pengolahan data menjadi grafik, diagram atau tabel tertentu sehingga orang dapat menarik kesimpulan dan mengambil keputusan.

–          System Software dan Aplication Software

System software merupakan perangkat lunak yang mengatur semua operasional dalam komputer, di dalamnya terdapat application software. Contohnya adalah windows, android, dll.

Aplication software adalah program yang didesain untuk meningkatkan kinerja user dan berinteraksi dengan teknologi komputer, yang ditanamkan dalam suatu system software.

–          Terdapat perbedaan terkait dengan kebutuhan saat pengumpulan data:

Functional Requirements : segala sumber data yang berkaitan dengan system yang ingin dibuat. Berkaitan dengan segala aktivitas dan layanan yang disediakan oleh system. Biasanya berhubungan dengan input, proses, output dan stored data. Contoh, dalam website binusmaya, kita harus mencari tahu data tentang system melihat perkuliahan, system melihat nilai mahasiswa, dll.

Non-functional requirements : Segala sumber data yang tidak terlalu terkait system tetapi penting. Biasanya berkaitan dengan performance, security atau cost. Contoh, dalam pembuatan suatu website, kita harus mengumpulkan data kira-kira berapa orang yang akan mengakses web tersebut sehingga web kita tetap memiliki performance yang baik meskipun diakses oleh banyak orang dalam suatu waktu tertentu.

–          Business Rules dan Business Constraints

Business Rules adalah apa informasi yang digunakan dan bagaimana cara perusahaan menggunakannya.

Business Constraints adalah data apa saja yang ada di database dan bagaimana data dapat diubah.

–          Database, Database Schema, Database Instance dan Metadata

Database itu adalah kumpulan data yang disimpan secara sistematis di dalam komputer dan dapat diolah atau dimanipulasi untuk menghasilkan suatu informasi.

Database schema adalah kumpulan dari berbagai entity yang ada bersama relasi-relasiny di dalam suatu instance atau storage. Atau bisa disebutkan bahwa database schema adalah deskripsi dari struktur database. Contohnya adalah ERD.

Capture

      Database Instance adalah data actual yang disimpan dalam waktu tertentu.

Metadata adalah isi dari data itu sendiri, data dalam data.

–          Membedakan Database dengan Penyimpanan Dile Sederhana

  1. Database mendeskripsikan dirinya sendiri

berisi deskripsi dari struktur yang digunakan untuk menyimpan data. Ia memiliki struktur yang berarti dan bukan hanya kumpulan file. Ini adalah kumpulan data yang saling berhubungan, bukan fakta acak.

  1. Software database dapat mengimplementasi rules integrity

Misalnya, jika tanggal harus disimpan, perangkat lunak database dapat memeriksa tanggal tersebut valid atau tidak sebelum disimpan.

–          Data Model dan Document Model

Data model adalah suatu pendekatan dalam mengatur dan mengorganisasi data.

3 aturan data model yang baik adalah

  1. Mendeskripsikan struktur data secara jelas.
  2. Menyediakan data dan data manipulation language.
  3. Menetapkan constraint untuk memastikan konsistensi dan akurasi data.

Document model adalah bagaimana sebuah dokumen dapat mendefinisikan secara jelas struktur dari konten. Tujuan dokumen model yaitu memungkinkan pengguna untuk menggunakan dokumen yang dapat digunakan bersama.

–          Web Database Technology

Web Browser adalah suatu software yang digunakan untuk mencari informasi dari suatu web. Contohnya adalah google chrome, safari, Mozilla firefox dan internet explorer.

Web Server adalah server yang digunakan untuk merequest sesuatu atau menerima respon dari server.

Database Management System(DBMS) adalah software yang mengelola semua interaksi yang dilakukan dengan database.

Database Client adalah software yang digunakan oleh end-user untuk berinteraksi dengan DBMS.

–          Web Konten Statis dan Dinamis

Website Statis adalah suatu web yang kontennya tidak berubah-ubah. Untuk mengubah suatu bagian dari web kita harus mengubah code dari web tersebut. Dengan kata lain, website statis hanya memiliki bagian front-end.

 Website Dinamis adalah web yang kontennya dapat berubah-ubah tanpa harus mengubah source code. Pengguna dapat mengubah melalui halaman yang telah disediakan (back-end) dengan melakukan request. Dengan kata lain, website dinamis memiliki dua bagian yaitu front-end dan juga back-end.

–          Distributed Database

Distributed database adalah beberapa database yang tersimpan di tempat yang berbeda-beda, yang kesemuanya terintegrasi menjadi satu. Berbeda dengan centralized database dimana database disimpan di dalam tempat yang sama.

Distributed database terdiri dari 2 yaitu Homogeneous dan Heterogeneous, perbedaannya adalah homogeneous dapat mengintegrasikan database-database di dalam 1 DBMS yang sama, sedangkan heterogeneous dapat mengintegrasikan database-database di DBMS yang berbeda.

 

www.binus.ac.id

  • Digg
  • Del.icio.us
  • StumbleUpon
  • Reddit
  • Twitter
  • RSS

Tugas II Teknik Kompilasi

Mengapa dalam top down parsing tidak boleh ada left recursive atau  left factoring?

Metode Top Down Parsing ada 2 jenis metode:

1. Backtrack/Backup: Brute Force

2. No Backtrack: Recursive Descent Parser

Metode Brute Forcer

Dalam metode Brute Forcer, grammar yang memiliki Left Recursion tidak bisa diperiksa, karena Left Recursion akan mengalami loopng atau perulangan secara terus-menerus atau tak terhingga. Sehingga perlu diubah terlebih dahulu menjadi grammar yang tidak mengandung Left Recursion.

Contoh:

E -> T | T + E | T – E

T -> F | F * T | F / T

F -> i

Grammar ini diterima karena tidak mengalami left recursive.

E -> E+T | E-T  | T

T -> T* F | T / F | F

F -> i

Grammar ini tidak diterima karena mengalami left recursive.

Dalam Top Down Parsing kita harus melakukan left factoring karena jika tidak melakukan left factoring, maka akan ada kemungkinan grammar tersebut mengalami ambiguitas. Left Factoring ini akan memperbaiki grammar yang ambigu (bila digambar dengan tree akan menghasilkan lebih dari 1 sintaks). Pada case – case tertentu, jika kita sudah melakukan eliminasi left recursion dan grammarnya sudah tidak ambigu tetapi kita masih tidak dapat menentukan “first” dari symbol tertentu, maka kita harus melakukan factorial.

Contoh:

–          Grammar sebelum melakukan left factoring

Untitled

–          Grammar Sesudah melakukan left factoring

 Untitled

Source : http://cse.spsu.edu/clo/teaching/cs4713/lecture/node28.html

www.binus.ac.id

  • Digg
  • Del.icio.us
  • StumbleUpon
  • Reddit
  • Twitter
  • RSS

Tugas I Teknik Kompilasi

RE : (ba|bb)*(a|b)*b

Ubah RE sampai DFA minimization, untuk mengubah RE menjadi DFA ada 2 cara yaitu menggunakan tree dan menggunakan cara NFA epsilon.

Cara I

  1. Pertama-tama kita membuat tree dari RE, dan memberikan node akhir dengan angka urut. Lalu kita menentukan Firstpost dan Lastpost dari setiap node, untuk nantinya menentukan start state. Hasil dari proses diatas dapat dilihat pada Gambar1 dibawah ini. So yang dihasilkan adalah {1,3,5,6,7}.

DSC_0321Gambar 1

            Dalam menentukan followpos, ada beberapa ketentuan:

a. Node akhir memiliki nilai false (not nullable) dan nilai dari first dan lastpost nya adalah sesuai dengan nomor urutnya.

b. untuk tanda ( | ) firspostnya adalah gabungan dari node kedua anaknya. Nilai true atau falsenya ditentukan dari kedua anaknya, jika keduanya true maka true, jika salah satu false maka false. (and relationship).

c. untuk tanda (*)  nilainya adalah nullable maka true, lalu firstpost nya adalah firstpos dari children 1 (kiri) dan lastpostnya dari children2(kanan).

d. untuk tanda (.)

– untuk firstpost, jika children1 (kiri) bernilai nullable(true) maka nilainya adalah gabungan dari firstpost c1(kiri) dan c2(kanan). Jika c1 tidak bernilai true maka firstpostnya adalah c1.

– untuk lastpost, jika children2 (kanan) bernilai nullable(true) maka nilainya adalah gabungan dari lastpost c1(kiri) dan c2(kanan). Jika c2 tidak bernilai true maka lastpostnya adalah c2.

e. untuk tanda (+)  nilainya adalah not nullable maka false, lalu firstpost nya adalah firstpos dari children 1 (kiri) dan lastpostnya dari children2(kanan).

2. Selanjutnya kita mencari Followpost untuk menemukan pergerakan/perpindahan dari satu input keinput lainnya. Proses tersebut dapat dilihat pada Gambar 2. Followpost adalah node mana yang mungkin dilalui saat kita ada di node tertentu.

DSC_0323Gambar 2

3. Langkah berikutnya yaitu mencari perpindahan state beserta inputnya, membutuhkan state awal {S0} yang telah didapat dari langkah 1, yaitu first post dari induk tree. Proses ini dimulai dari state awal{S0}, dan di setiap state kita cari pergerakan dari state tersebut bila diberikan input yang ada (pada soal ini input nya{a,b}), lalu kita hubungkan dengan Followpost dari langkah 2 (Gambar 2). Bila hasil penelusuran tidak sama dengan state yang telah ada maka dibuat state baru dan dicari lagi dengan proses diatas. Dan bila di state tersebut terdapat angka Lastpost {8} di Gambar 1 maka state tersebut dijadikan finish state (*). Hasil proses ini dapat dilihat pada Gambar 3.

Contoh pengerjaan:

{So} berisi {1,3,5,6,7}. Untuk input a, cari di antara nomor 1,3,5,6,7 yang mengandung a, yaitu nomor 5. Maka kita tuliskan So input a adalah followpos dari 5 yaitu {5,6,7} dan seterusnya.

DSC_0324 Gambar 3

Dan dari Gambar 3 kita dapat menggambarkan setiap state lalu menghubungkan setiap state sesuai dengan hasil dari input yang diberikan. Hasilnya dapat dilihat pada Gambar 4.

DSC_0328Gambar 4

Cara II –NFA Epsilon

  1. Gambarkan NFA Epsilon dari RE.DSC_0334
  2. Data node dan closure dari setiap input. Mulai dari mencari So. So didapat dari e-closure node yang paling pertama yaitu node 0. Cek node 0 jika diinput epsilon akan ke node mana saja. Node-node tersebut menjadi S1. Selanjutnya cek node S1 dan seterusnya, bila diberi input a atau input b, maka node hasil inputan a atau b tersebut akan mengarah ke node apa saja bila diberi input epsilon.DSC_0333
  3. Hasil DFA nya. Hasil DFA dari cara tree maupun NFA epsilon akan sama.DSC_0328

DFA Minimization

Setelah kita menemukan DFA seperti pada Gambar 4 maka kita juga dapat menentukan DFA Minimazion. DFA Minimization dapat ditemukan dengan cara kita memisahkan antara final state dan yang bukan final state dan kita beri pengelompokan tersebut dengan nilai index (1,2) seperti yang dapat kita lihat pada Gambar 5. Dan kemudian kita telusuri kembali setiap state tersebut, contoh kita mulai dari state S0lalu kita beri input a, kita lihat pada Gambar4 kemana S0 akan pindah bila diberi input tersebut. Disini kita lihat input a akan membuat perpindahan ke state S1 dan kita lihat lagi pada Gambar5, berada diindex manakah S1, dan S1 terdapat diindex 1, maka kita berikan tanda index di sebelah kiri atas (1S1), lalu kita input S0 dengan b, kemanakah dia akan berpindah dan hasil perpindahan tersebut ada diindex berapa dan kita berikan tanda index lagi (2S2). Dan proses diteruskan hingga semua state telah ditelusuri.

tabel minGambar 5

Lalu setelah kita mencari hasil perpindahannya kita kelompokan lagi setiap state yang akan menuju state dan index yang sama dan berikan setiap state index baru. Gambar dapat dilihat pada bagian bawah. State yang memiliki index yang sama nanti nya akan dijadikan 1 state (Gambar 6).

Lalu setelah kita menemukan state mana yang dijadikan index yang sama maka langkah selanjutnya adalah kita menggambarkan state yang ada diman state dengan index yang sama dijadikan kedalam satu node. Proses tersebut dapat dilihat pada Gambar 6.

dfaminGambar 6

www.binus.ac.id

Tags: , , , ,

  • Digg
  • Del.icio.us
  • StumbleUpon
  • Reddit
  • Twitter
  • RSS

First Post

Hello World 🙂

  • Digg
  • Del.icio.us
  • StumbleUpon
  • Reddit
  • Twitter
  • RSS

Hello world!

Welcome to Binusian blog.
This is the first post of any blog.binusian.org member blog. Edit or delete it, then start blogging!
Happy Blogging 🙂

  • Digg
  • Del.icio.us
  • StumbleUpon
  • Reddit
  • Twitter
  • RSS