PERTEMUAN 5 & 6 TENTANG NFA DAN DFA

Definisi Otomata

Otomata adalah Suatu bentuk/model matematika yang memiliki fungsi-fungsi dari komputer digital yaitu :

1. menerima input,
2. menghasilkan output
3. bisa memiliki penyimpanan sementara
4. mampu membuat keputusan dalam mentransformasikan input ke output

Otomata terdiri dari sejumlah berhingga state (kedudukan). Perpindahan state satu ke yang lain berdasar input dan fungsi transisi. Otomata membuat keputusan apakah input diterima atau tidak.

Contoh 1 :  

Memiliki 6 state: q0, q1, q2, q3, q4, q5
State awal: q0 ditandai dengan panah masuk tanpa state sebelumnya
State akhir: {q3. q4} ditandai dengan lingkaran dobel
Himpunan input: {a, d, u}

Q = {q0, q1, q2, q3, q4, q5}
Σ = {a, d, u}
S = q0

F = {q3, q4}
δ = fungsi transisi
δ(q0, a) = q1
δ(q1, d) = q2
δ(q2, a) = q3
δ(q2, u) = q4
δ(q2, d) = q5

Contoh 2: Mesin jaja Definisi formal FSA

 

Q = {q0, q5, q10, q15, q20, q25}
Σ = {5, 10, 15}
S = q0

F = {q25}
δ = fungsi transisi
δ(q0, 5) = q5

δ(q0, 25) = q25

δ(q0, 10) = q10

δ(q5, 5) = q10

δ(q5, 10) = q15

δ(q10, 5) = q15

δ(q10, q10) = q20

δ(q15,10) = q25

δ(q15, 5) = q20

δ(q20, 5) = q25

 

 

DEFINISI FORMAL FSA

M = (Q,Σ,δ,S,F) di mana :
Q = himpunan state
Σ = abjad, himpunan simbol input/masukan
δ = fungsi transisi, δ : Q x Σ à Q
S = state awal / initial state
F = himpunan state akhir/final state

JENIS FSA

• Deterministik (DFSA/DFA) Pada setiap input, hanya ada satu keadaan (state) tujuan dari keadaan saat ini.
• Nondeterministik (NFSA/NFA)
  pada setiap input terdapat lebih dari satu keadaan tujuan dari keadaan saat ini.
  
  

Deterministic Finite Automata(DFA)
Dari suatu state ada tepat satu state berikutnya untuk setiap simbol masukan yang diterima

D-FSA/DFA

• Himpunan keadaan (Q).
• Himpunan simbol input (S)
• Fungsi transisi (d), memuat satu keadaan asal dan satu simbol input dan satu keadaan tujuan. Keadaan awal (q0)merupakan salah satudari Q.
• Himpunan keadaan final atau yang diterima, dinotasikan dengan F (FÍQ)

5-TUPLE D-FSA

DFSA A, terdiri atas 5 tuple, yaitu:

A = (Q, S,d, q0, F)

Notasi Lain DFSA

1. Diagram Transisi / State Diagram

• Tiap keadaan merupakan simpul
• Tiap keadaan q Î Q dan tiap simbol a Î S, dituliskan sebagai d(q,a) = p.Artinya, diagram transisi memiliki panah dari q ke p, yang berlabel a.
• Keadaan awal (q0) ditandai dengan adanya panah tanpa sumber.
• Simpul yang menjadi keadaan final ditandai dengan lingkaran bergaris tepi ganda

 

2. Tabel Transisi

• Representasi daftar dari suatu fungsi
• Baris menunjukkan keadaan dan kolom menunjukkan input.
• Isi dari baris menunjukkan keadaan q dan isi dari kolom input a menunjukkan keadaan d

Contoh:

DFSA yang dapat menerima string berakhiran 01

A = ({q0, q1, q2}, {0,1}, d, q0, {q2})

dengan fungsi transisi d diberikan dalam bentuk tabel:

Contoh DFSA :
M = (Q, S, d, s, F), dimana :

Q = {q0, q1},
S = {a,b},
S = q0,
F = {q0}

 

 

 

 

 

 

 

Jika M diberi input aabba,dengan state awal (q0,aabba),maka :
(q0,aabba) ├M (q0,abba)
├M (q0,bba)
├M (q1,ba)
├M (q0,a)
├M (q0,e)

Karena (q0,aabba) ├*M (q0,e),jadi aabba diterima oleh M

Contoh: DFSA yang dapat menerima semua string berakhiran 01

Contoh : diberikan input pada mesin DFSA 110111, lakukan tracer :
(q0,110111) ├M (q0,10111)
├M (q0,0111)
├M (q1,111)
├M (q1,11)
├M (q1,1)
├M (q1,e)

Karena berhenti bukan di q2, maka 110111 tidak diterima oleh mesin DFSA

Contoh: DFSA yang dapat menerima semua string berakhiran 01

 

 

 

Contoh : diberikan input pada mesin DFSA 10110, lakukan tracer :
(q0,10110) ├M (q0,0110)
├M (q1,110)
├M (q1,10)
├M (q1,0)
├M (q2,e)
Karena berhenti di q2, maka 10110 diterima oleh mesin DFSA

DFA nya
Q = {q0 , q1 , q2 , q3 }
S = {0,1}
S = q0
F = { q0}

Contoh : diberikan string 011 dan 1010, buktikan bahwa string tersebut diterima atau ditolak !
d(q0,011) = d(q2,11) = d(q3,1) = q2 Ditolak
d(q0,1010)                 = d(q1,010)
                                   = d(q3,10)
                                   =d(q2,0)
                                   = d(q0,e) Diterima

Contoh Soal: DFA

Σ = {0,1}

Q = {a, b, c, d}

S = {a}

F = {b, c}

Fungsi transisi δ : Q x Σ à Q, yang didefinisikan sebagai :

δ = {((a,0),b), ((a,1),d), ((b,0),c), ((b,1),d), ((c,0),d), ((c,1),c), ((d,0),a), ((d,1),b)}

Fungsi transisi dapat ditulis dalam bentuk tabel

 

FINITE STATE OTOMATA

A. PENGERTIAN

FSA (Finite State Automata) merupakan tool yang sangat berguna dalam perancangan lexical analyzer, yaitu bagian dari kompilator yang mengelompokan karakter-karakter ke dalam sebuah token, yang berupa unit terkecil seperti nama, variabel, dan keyword. FSA dipakai untuk penganalisa leksikal dan dipakai juga dalam text editor, pemrosesan teks, dan program file-searching

FSA dapat juga sebagai :

• Model matematika suatu sistem yang menerima input dan output diskrit
• Mesin automata dari bahasa Regular
• Tidak memiliki tempat penyimpanan sehingga kemampuan mengingat terbatas (contoh: elevator/lift)
• Aplikatif - berguna untuk merancang sistem
  nyata.
• Aplikasi meliputi : analisis leksikal, text-editor, protokol komunikasi jaringan (kermit) dan parity checker (pengecek parity).

FSA atau AH (Automata Hingga) didefinisikan sebagai pasangan 5 tupel à M = (Q, ∑, δ, S, F).

1. Q : himpunan hingga state
2. ∑ : himpunan hingga simbol input (alfabet)
3. δ : fungsi transisi, menggambarkan transisi state FSA akibat pembacaan simbol input. Fungsi transisi ini biasanya diberikan dalam bentuk tabel.
4. S Î Q : state AWAL
5. F Í Q : himpunan state AKHIR

 

 

Mesin ini memiliki 6 state (q0,q1,q2,q3,q4,q5). State awal q0, q3 dan q4 adalah state akhir, sedangkan simbol input adalah (a,d,u)


CONTOH

Contoh : FSA untuk mengecek parity ganjil

Q ={Gnp, Gjl}

∑ = {0,1}

TABEL TRANSISI

S = Gnp, F = {Gjl}

CONTOHGjl Gjl Gnp
Seorang petani dengan seekor serigala, kambing dan seikat rumput berada pada suatu sisi sungai. Tersedia hanya sebuah perahu kecil yang hanya dapat dimuati dengan petani tersebut dengan salah satu serigala, kambing atau rumput. Petani tersebut harus menyeberangkan ketiga bawaannya kesisi lain sungai. Tetapi jika petani meninggalkan serigala dan kambing pada suatu saat, maka kambing akan dimakan serigala. Begitu pula jika kambing ditinggalkan dengan rumput, maka rumput akan dimakan oleh kambing. Mungkinkah ditemukan suatu cara untuk melintasi sungai tanpa menyebabkan kambing atau rumput dimakan.

 

 

 

 

 

SSH (Secure Shell)

SSH merupakan singkatan dari Secure Shell yang adalah aplikasi pengganti remote login seperti telnet, rsh, dan rlogin, yang jauh lebih aman. Fungsi utama aplikasi ini adalah untuk mengakses mesin secara remote. Sama seperti telnet, SSH Client menyediakan User dengan  Shell untuk remote ke mesin. Tidak seperti telnet, SSH menyediakan koneksi enkripsi antara klien dengan server. Dalam prakteknya, penggunaan menggunakan telnet dan ssh seperti perbedaan dengan mengakses website biasa dengan website yang lebih aman (HTTPS). SSHdirancang untuk menggantikan service-service di sistem unix/linux yang menggunakan sistemplain-text seperti telnet, ftp, rlogin, rsh, rcp, dll). 

Untuk menggantikan fungsi ftp dapat digunakan sftp (secure ftp), sedangkan untukmenggantikan rcp (remote copy) dapat digunakan scp (secure copy). Dengan SSH, semuapercakapan antara server dan klien di-enkripsi. Artinya, apabila percakapan tersebutdisadap, penyadap tidak mungkin memahami isinya. Implementasi SSH yang banyak dipakai saatini adalah OpenSSH. Aplikasi ini telah dimasukkan kedalam berbagai macam distribusi linux. Redhat Linux versi 9 sudah menyediakan program tersebut dalam format RPM. 

Protokol SSH menyediakan layanan sebagai berikut :

• Pada saat awal terjadinya koneksi, client melakukan pengecekkan apakah host yang dihubungi sudah terdaftar pada client atau tidak.
• Client mengirimkan proses autentifikasi ke server menggunakan teknik enkripsi 128 bit.
• Semua data yang dikirimkan dan diterima menggunakan teknik enkripsi 128 bit sehingga sangat sulit dibaca tanpa mengetahui kode enkripsinya.
• Client dapat memforward aplikasi Xwindows/X11 ke server, layanan ini dibuat.

Cara Kerja SSH :

• Langkah 1 : Client melakukan koneksi ke port SSH ( 22 ) dan mengirimkan sebuah pesan bahwa client ingin membentuk sebuah hubungan informasi yang aman
• Langkah 2 : Client dan server menyetujui untuk menggunakan sesi SSH tertentu. Nah, sesi disini dalam arti apakah menggunakan SSHv1 atau SSHv2. Kedua belah pihak harus menggunakan versi SSH yang sama. Kemudian kedua belah pihak membentuk 2 key yang nantinya digunakan untuk mengamankan informasi yaitu Public key dan Private Key.
• Langkah 3 : Client meminta Public Key dan Host Key milik Server begitu juga sebaliknya, Server meminta Public key dan Host Key milik Client.
• Langkah 4 : Server-Client Setuju untuk menggunakan algoritma tertentu ketika melakukan enkripsi nantinya, misal menggunakan DES.
• Langkah 5 : Client melakukan Enkripsi Host Key dengan Public Key Server kemudian dikirimkan ke Server dan Server melakukan Decrypt dengan mengggunakan Private Key yang dimiliki oleh Server hal yang sama juga di lakukan oleh Server. Hal ini dilakukan untuk proses otentikasi bahwa memang benar peer pasangannya lah yang hanya bisa melakukan proses pengaman informasi dengan SSH.
• Langkah 6 : Sampai disini koneksi telah terbentuk, dan client dapat selanjutnya bekerja secara interaktif pada server atau mentransfer file ke atau dari server. Informasi antar Client Sudah Bisa dilakukan.

DES adalah salah satu protokol enkripsi secret key untuk membantu memastikan privacy dari keseluruhan komunikasi yang dimulai dengan username/password awal. Implementasi SSH pada Linux diantaranya adalah OpenSSH. Dengan Private SSH dapat menyembunyikan IP asli Anda, browsing yang aman, membuka situs yang diblokir dan tentu saja mempercepat koneksi internet.

Manfaat SSH :

• Dengan menggunakan SSH kita dapat bergerak bebas melalui struktur file akun hosting.
• Kita juga dapat menjalankan tugas seperti monitoring log file dan memulai atau menghentikan service. Bahkan kita juga dapat menggunakannya untuk install software ke akun hostingmu atau manage database MySQL. 
• SSH mengijinkan Kita untuk melakukan banyak hal lebih dari standard web. 

Di bawah ini merupakan pengoperasian SSH pada CentOS :

• Untuk mengecek paket SSH, ketikkan perintah $ rpm -qa | grep ssh.

• Untuk melakukan file konfigurasi pada SSH harus masuk sebagai super user terlebih dahulu. Setelah masuk, ketikkan perintah # vi /etc/ssh/sshd_config .

• Untuk melakukan SSH kepada komputer atau server lain ketikkan perintah # ssh [server]@[IP_server]. Pada gambar di bawah saya melakukan SSH pada server OS20.

• Untuk melakukan akses SSH tanpa login gunakan perintah $ ssh -keygen -t dsa . Setelah itu, lakukan perintah # ssh [server]@[IP_server] untuk masuk ke server tersebut.
• 
  
  
  
  
  
• Untuk mengirim file ke server lain ketikkan perintah-perintah seperti gambar di bawah . Pada gambar di bawah saya mengirimkan file kepada server OS20.
• 
  
  

BLOCKING & BUFFERING

Blocking adalah Penempatan sejumlah record pada suatu block. Block adalah unit data yang ditransfer. Block berukuran tetap berisi sekumpulan karakter yang dipindah dari penyimpan ke memori atau sebaliknya. 

Ada 3 metode blocking :

1. Fixed Blocking
2. Variable-Length Spanned Blocking
3. Variable-Length UnSpanned Blocking

Record adalah unit untuk penyimpanan data di level logik atau file. Ukuran rekord :

1. Berukuran tetap (fixed record)
2. Berukuran variabel (variable record)

A. Fixed Blocking

Fixed Blocking adalah Jumlah record pada suatu block sama dengan jumlah record pada block yang lainnya.

Batasan dalam penggunaan metode ini :

1. Fixed length record
2. Record length <= Block Size
3. Blocking Factor (Bfr) = [B/R]

Blocking factor adalah jumlah record yang dapat ditampung didalam satu block.

B. Variable - Lenght Spanned Blocking

Block berisi record-record dengan panjang tidak tetap.

Jika satu record tidak dapat dimuat disatu block, sebagian record disimpan di block lain.

B = Block Size

P = Block Pointer

R = Panjang Record rata-rata

M = Record Mark

C. Variable – Lenght Unspanned Blocking

Block berisi record-record dengan panjang tidak tetap. Setiap record harus dimuat di satu block.

B = Block Size

R = Panjang Record rata-rata

ORGANISASI BERKAS - BERKAS SEKUENSIAL

ORGANISASI BERKAS

Organisasi berkas diatas memiliki kemampuan untuk diproses dengan metode pemprosesan & pengaksesan yang berbeda.

Dalam menggorganisasi berkas secara Sekuensial, Langsung, maupun Sekuensial Berindeks memiliki cara yang berbeda dalam penyusunan rekaman-rekaman yang membentuk berkas / file tersebut. Rekaman-rekaman data tersebut tersusun atas sejumlah medan Data.

Medan Data : Nilai Dasar yang membentuk sebuah rekaman Data

Rekaman Data : Koleksi Berbagai Medan yang berisi beberapa item data elementer

Berkas Data : koleksi dari rekaman-rekaman yang sama, yang diletakan dalam peralatan penyimpanan data komputer.

Rekaman Data

Contoh rekaman data mahasiswa

Contoh berkas mahasiswa sebuah universitas

BERKAS SEKUENSIAL

Dalam berkas Sekuensial, rekaman ke i+1 akan diletakan tepat sesudah rekaman ke-i,  sebagai contoh :

Pencarian berkas sekuensial

Pencarian berkas secara sekuensial dilakukan dengan memproses rekaman-rekaman dalam berkas sesuai dengan urutan keberadaan rekaman-rekaman tersebut sampai ditemukan rekaman-rekaman yang diinginkan atau semua rekaman akan terbaca.

Contoh “nama mahasiswa” merupakan subskrip dalam pencarian pembacaan rekaman dengan “nama mahasiswa” = “Dewi Sartika”

Untuk mencari nama “Dewi Sartika”, diperlukan probe sejumlah 5 kali

Permasalahan yang muncul bila rekaman berada pada urutan belakang, maka pembacaan akan semakin lama. Dan apabila nama yang dicari tidak ada dalam rekaman, maka aplikasi harus membaca semua rekaman & berakshir denganm pesan “Rekaman tidak ditemukan”

Agar kinerja pembacaan rekaman lebih baik maka salah satu alternatif yang dapat dilakukan adalah rekaman-rekaman dalam berkas tersebut DIURUTKAN untuk mendapatkan pengurutan yang linier berdasar pada nilai kunci rekaman tersebut (bisa alfabetis maupun numeris)

Kolom “Nama Mahasiswa” menunjukan nilai yang urut dari kecil ke besar

Setelah data tersebut diurutkan maka pembacaan secara sekunsial dalam pemprosesan pencarian nama “Dewi Sartika” hanya diperlukan 2 probe lebih kecil dibandingkan sebelum berkas diurutkan.

PENCARIAN BINER (BINARY SEARCH)

Untuk sebuah berkas yang sudah di urutkan, jumlah probe yang diperlukan untuk membaca sejumlah rekaman dapat di usahakan untuk diperkecil lagi dengan menggunakan teknik pencarian biner.

Jika Kuncicari < Kuncitengah, maka bagian berkas mulai dari Kuncitengah sampai akhir berkas dielaminiansi.

Contoh 1

Cari rekaman dengan kunci 49 .... ?

                 1     2    3   4    5   6     7   8    9

Iterasi 1 : [21, 25, 28, 33, 38, 39, 48, 49, 69]

Iterasi 2 :  21, 25, 28, 33, 38, [39, 48, 49, 69]

Iterasi 3 :  21, 25, 28, 33, 38, 39, 48, [49, 69]

Perhitungan :

Iterasi 1           : TENGAH1 = [1+9)/2] = 5

            Kuncicari : Kuncitengah à 49 > 38

            AWAL = TENGAH1  + 1 = 5+1 = 6

        1     2    3    4    5    6     7   8    9

 Iterasi 1 : [21, 25, 28, 33, 38, 39, 48, 49, 69]                                                                                                                                               

Iterasi 2           : TENGAH2 = [6+9)/2] = 7

            Kuncicari : Kuncitengah à 49 > 48

           AWAL = TENGAH2  + 1 = 7+1 = 8

                  1    2    3    4    5    6     7   8    9

Iterasi 2 :  21, 25, 28, 33, 38, [39, 48, 49,69]                                                                                                                                   

Iterasi 3           : TENGAH3 = [8+9)/2] = 8

            Kuncicari : Kuncitengah à 49 = 49

            Ketemu, Probe = 3

                  1    2    3    4    5    6     7   8    9

Iterasi 3 :  21, 25, 28, 33, 38, 39, 48, [49, 69]

PENCARIAN INTERPOLASI

Pencarian Interpolasi menentukan posisi yang akan diperbandingkan berikutnya berdasarkan posisi yang diestimasi dari sisa rekaman yang belum diperiksa. Syarat dalam pencarian berkas dalam pencarian interpolasi adalah kunci rekaman adalah bilangan numeris, karena dalam proses pencarian interpolasi posisi rekaman yang akan dibandingkan dihitung dengan melibatkan proses aritmatik tehadap kunci awal, kunci akhir, dan kunci yang di cari. Kunci awal adalah kunci awal pada posisi pencarian terakhir, bukan kunci awal berkas.

Untuk mencari kunci berikutnya pada metode Interpolasi dapat menggunakan :

Jika Kunci (dicari) = Kunci (berikut), maka pencarian berakhir

Jika Kunci (dicari) > kunci (berikut), maka AWAL = BERIKUT + 1

Jika Kunci (dicari) < kunci (berikut), maka AKHIR = BERIKUT - 1

CONTOH 1

Untuk rekaman dengan susunan sebagai berikut :

               1   2    3    4     5    6    7    8    9

            [21, 25, 28, 33, 38, 39, 48, 49, 69]

Berapa probe untuk menentukan rekaman dengan kunci 49 bila menggunakan pencarian interpolasi ?

            1      2    3     4    5    6    7   8     9

Iterasi 1 :         [21, 25, 28, 33, 38, 39, 48, 49, 69]

Iterasi 2 :         21, 25, 28, 33, 38, 39, [48, 49, 69]

Perhitungan :

Iterasi 1           Berikut1 = 1 + ((49-21)/(69-21)) (9-1) = 5.66666 ≈ 5

Kcari banding Kberikut = 49 > 38, Maka AWAL = Berikut1 + 1 = 5+1 =6

 1     2    3    4    5     6   7    8     9

Iterasi 1 :        [21, 25, 28, 33, 38, 39, 48, 49, 69]

Iterasi 2           Berikut2 = 6 + ((49-39)/(69-39)) (9-6) = 7

Kcari banding Kberikut = 49 > 48, Maka AWAL = Berikut2 + 1 = 7+1 =8

                         1    2   3    4     5    6    7    8     9

Iterasi 2 :        21, 25, 28, 33, 38, [39, 48, 49, 69]

Iterasi 3           Berikut3 = 8 + ((49-49)/(69-49)) (9-7) = 8

Kcari banding  Kberikut = 49 = 49, Maka Ketemu, Probe = 3

                         1    2   3    4    5    6    7     8     9

Iterasi 3 :        21, 25, 28, 33, 38, 39, 48, [49, 69]