Selasa, 01 Juni 2021
Senin, 31 Mei 2021
Rabu, 19 Mei 2021
Standar Uji Perangkat Lunak
5 Metode Pengujian Tentang Security
Sebelum kita menjelaskan 5 metode pengujian tentang security, kita harus mengetahui terlebih dahulu apa itu security testing
Pengertian Security Testing
Security testing merupakan jenis pengujian software yang dilakukan untuk mengidentifikasi kerentanan serta memastikan bahwa data dan sumber daya sistem di dalamnya sudah terlindungi dengan baik dari para peretas. Pada setiap pengujian pasti memiliki tujuan, maka tujuan dari pengujian ini untuk menemukan semua celah dan kelemahan sistem yang dapat mengakibatkan hilangnya informasi atau reputasi.
Dalam security testing khususnya yang dilakukan pada situs website dan aplikasi, akan ada empat area utama yang akan diperhatikan adalah:
- Network security: Pengujian ini dilakukan untuk mencari kerentanan dalam infrastruktur jaringan.
- System software security: Pengujian untuk menilai bagaimana tingkat kelemahan berbagai perangkat lunak tempat aplikasi bekerja seperti operating system, database system.
- Client-side application security: pengujian ini dapat memastikan bahwa sisi klien seperti browser tidak dapat dimanipulasi.
- Server-side application security: pengujian untuk memastikan bahwa sisi server memiliki keamanan yang kuat dan dapat memblokir beragam gangguan.
5 Metode Pengujian Tentang Security
1. Security Scanning
Pemindaian keamanan adalah awal yang baik untuk memeriksa status keamanan. Selama pemindaian, memeriksa risiko keamanan apa yang harus ditangani dalam infrastruktur TI tertentu. Ini adalah pemeriksaan cepat untuk potensi kebocoran keamanan, risiko jaringan, dan masalah keamanan. Security scanning dilakukan untuk menyingkirkan ancaman dunia maya untuk selamanya. Dengan melakukan pemindaian keamanan, bisnis dapat melindungi diri mereka sendiri dari ancaman serangan dunia maya yang terus berkembang.
2. Security Auditing
Audit keamanan jaringan adalah penilaian atau evaluasi teknis yang sistematis dan terukur mengenai keamanan komputer dan aplikasinya. Audit keamanan jaringan ini terdiri dari dua bagian, yaitu:
- Penilaian otomatis : berkaitan dengan pembuatan laporan audit yang dijalankan oleh suatu perangkat lunak terhadap perubahan status file dalam komputer: create, modify, delete.
- Penilaian non-otomatis : berhubungan dengan kegiatan wawancara kepada staff yang menangani komputer, evaluasi kerawanan dan keamanan komputer, pengamatan terhadap semua akses ke sistem operasi dan software aplikasinya, serta analisis semua akses fisik terhadap sistem komputer secara menyeluruh.
Tahapan dilakukan scanning network dengan memanfaatkan berbagai tools network scanning dan vulnerability scanner online. Tujuan yang ingin dicapai adalah memperoleh informasi vulnerability network tersebut, misal daftar port yang terbuka, bug pada aplikasi server, dan lain-lain yang biasanya fase ini disebut sebagai passive attack.
4. Risk Assesment
Penilaian risiko adalah pandangan menyeluruh untuk mengidentifikasi hal-hal, situasi, proses, dll. yang dapat menyebabkan kerugian, terutama bagi orang-orang. Setelah identifikasi dibuat, selanjutnya lakukan analisis dan evaluasi seberapa besar kemungkinan dan seberapa parah risikonya. Ketika keputusan telah dibuat maka selanjutnya dapat memutuskan tindakan apa yang harus dilakukan untuk secara efektif menghilangkan atau mengendalikan kerusakan yang terjadi. Penilaian risiko bisa juga dibilang sebagai istilah yang digunakan untuk menggambarkan keseluruhan proses atau metode di mana:
- Identifikasi bahaya dan faktor risiko yang berpotensi menyebabkan bahaya (identifikasi bahaya).
- Menganalisis dan mengevaluasi risiko yang terkait dengan bahaya itu (analisis risiko, dan evaluasi risiko).
- Tentukan cara yang tepat untuk menghilangkan bahaya, atau kendalikan risiko bila bahaya tidak dapat dihilangkan (pengendalian risiko).
5. Penetration Testing
Penetration Testing atau Pen Testing adalah jenis pengujian keamanan yang digunakan untuk mengungkap kerentanan, ancaman, dan risiko yang dapat dieksploitasi oleh penyerang dalam aplikasi perangkat lunak, jaringan, atau aplikasi web. Tujuan pengujian penetrasi adalah untuk mengidentifikasi dan menguji semua kemungkinan kerentanan keamanan yang ada dalam aplikasi perangkat lunak. Pengujian penetrasi juga disebut Pen Test. Penetrasi sangat penting dalam suatu perusahaan karena:
- Sektor keuangan seperti Bank, Perbankan Investasi, Bursa Perdagangan Saham ingin datanya diamankan, dan pengujian penetrasi sangat penting untuk memastikan keamanan.
- Jika sistem perangkat lunak sudah diretas dan organisasi ingin menentukan apakah masih ada ancaman dalam sistem untuk menghindari peretasan di masa mendatang.
- Pengujian Penetrasi Proaktif adalah perlindungan terbaik terhadap peretas.
- Black box testing: penguji tidak memiliki pengetahuan tentang sistem yang akan diuji. Dia bertanggung jawab untuk mengumpulkan informasi tentang jaringan atau sistem target.
- White box testing: penguji biasanya diberikan informasi lengkap tentang jaringan atau sistem yang akan diuji termasuk skema alamat IP, kode sumber, detail OS, dll. Ini dapat dianggap sebagai simulasi serangan oleh siapapun. Sumber internal (Karyawan Organisasi).
- Grey box testing: penguji diberikan pengetahuan parsial tentang sistem. Ini dapat dianggap sebagai serangan oleh peretas eksternal yang telah memperoleh akses tidak sah ke dokumen infrastruktur jaringan organisasi.
Sumber :
Rabu, 07 April 2021
REVIEW MATERI
DASAR-DASAR UJI PERANGKAT LUNAK
Pengujian bertujuan untuk mencari kesalahan. Pengujian yang baik adalah pengujian yang memiliki kemungkinan besar dalam menemukan kesalahan.
Karakteristik pengujian menurut Kaner, Falk, dan Nguyen [Kan93] menggambarkan atribut-atribut sebagai berikut untuk pengujian yang "baik" :
- Pengujian yang baik memiliki probabilitas tinggi untuk menemukan kesalahan. Tujuan pengujian ini harus memahami perangkat lunak dan mencoba untuk mengembangkan sebuah gambaran bagaimana perangkat lunak bisa gagal;
- Pengujian yang baik tidak berulang-ulang. Tidak ada manfaatnya jika melakukan pengujian yang memiliki tujuan yang sama dengan pengujian yang lain;
- Pengujian yang baik harus menjadi "bibit terbaik". Keterbatasan waktu dan sumber daya dapat mengurangi pelaksanaan bahkan hanya sebagian kecil dari pengujian ini;
- Pengujian yang baik harus tidak terlalu sederhana atau terlalu rumit. Meskipun memungkinkan untuk menggabungkan serangkaian pengujian menjadi satu kasus pengujian saja, akan mengakibatkan terjadinya banyak kesalahan yang harus ditutupi. Secara umum, pengujian harus dilaksanakan secara terpisah.
Pengujian perangkat lunak (software testing) adalah suatu teknik yang digunakan untuk menentukan bahwa perangkat lunak yang dihasilkan telah memecahkan masalah.
Tiga konsep yang harus diperhatikan dalam Pengujian Perangkat Lunak:
- Demonstrasi validitas perangkat lunak pada setiap tahapan pembangunan sistem;
- Penentuan validitas sistem akhir terhadap pemakai dan kebutuhan;
- Pemeriksaan implementasi sistem dengan menjalankan sistem pada suatu contoh data uji.
Dua kelas imput yang disediakan untuk proses uji perangkat lunak:
- Konfigurasi software termasuk software requiment specification, design specification, dan source code;
- Konfigurasi uji termasuk test plan & procedure, perangkat testing yang akan digunakan, test case dan hasil yang diharapkan.
Kemampuan sebuah perangkat lunak untuk bisa diuji:
- Kemampuan untuk bisa dioperasikan (Operability). Jika dirancang dan diimplementasikan dengan kualitas, relative sedikit kesalahan yang akan menghambat pelaksanaan penguji yang memungkinkan penguji berlanjut tanpa penyesuaian dan mulai dari awal;
- Kemampuan untuk bisa diobservasi (Observability). Input tersedia sebagai bagian dari pengujian yang menghasilkan output berbeda. Bagian dan variabel sistem terlihat atau dapat dipertanyakan selama eksekusi output yang salah bisa dengan mudah diidentifikasi;
- Kemampuan untuk dapat dikontrol (Controllability). Semua output yang mungkin dapat dihasilkan melalui beberapa kombinasi dari input, dan format I/O konsisten dan terstrukur. State dan variabel dari perangkat lunak dan perangkat keras dapat dikontrol langsung oleh penguji;
- Kemampuan untuk dapat disusun (Decomposability). Sistem perangkat lunak dibangun dari modul independen yang dapat diuji secara independen pula;
- Kesederhanaan (Simplicity). Program ini harus menunjukan kesederhanaan fungsionalitas, kesederhanaan structural, kesederhanaan kode;
- Stabilitas (Stability). Perubahan pada perangkat lunak jarang dikontrol ketika perubahan itu terjadi dan tidak membatalkan pengujian-pengujian yang telah ada. Perangkat lunak ini pulih melalui kegagalan;
- Kemampuan untuk bisa dipahami (Understandability). Perancangan arsitektur dan ketergantungan antara komponen-komponen internal, eksternal, dan yang dipakai bersama dipahami dengan baik. Dokumentasi teknis dapat langsung diakses, terorganisasi dengan baik, spesifik dan terperinci, dan akurat. Perubahan rancangan perlu dikomunikasikan dengan penguji.
TYPE TESTING
Di dalam suatu perusahaan IT atau website production yang memproduksi software atau website, pastinya memiliki 1 atau bahkan 3 orang software tester yang bertugas melakukan testing software atau website, seorang quality assurance atau tester bertugas mempersiapkan kasus pengujian untuk setiap case dan skenarionya menyelesaikan aktivitas persyaratan suatu sistem.
Dua jenis acceptance testing biasa dilakukan oleh perusahaan pengembang perangkat lunak, yakni:
- Alpha Test ⇒ Pengujian yang dilakukan pada perangkat lunak oleh end-user dengan adanya supervisi dan kontrol dari pengembang perangkat lunak;
- Beta Test ⇒ Pengujian yang dilakukan pada perangkat lunak oleh end-user tanpa adanya supervisi dan kontrol dari pengembang perangkat lunak. Jika ditemukan masalah, maka konsumen pemakai akan melaporkannya kepada pengembang perangkat lunak tersebut.
Sembilan jenis-jenis pengujian yang perlu diketahui oleh seorang quality assurance pada software, yaitu:
- System Testing ⇒ Pengujian untuk memastikan bahwa keseluruhan sistem tidak berfungsi dan bahwa sistem telah memenuhi persyaratan pengguna (user requirement). System testing biasanya dilakukan di akhir setiap iterasi untuk mengidentifikasi isu-isu penting, seperti masalah performance dari software. Biasanya test ini harus dilakukan sesering mungkin;
- Unit Testing ⇒ Pengujian software di mana QA menguji suatu unit program layak untuk tidaknya dipakai. Unit testing ini fokusnya pada pengujian unit yang terkecil pada desain perangkat lunak (komponen atau modul perangkat lunak). Karena dalam sebuah software banyak memiliki unit-unit kecil maka untuk mengujinya biasanya dibuat program kecil atau main program untuk menguji unit-unit software. Unit-unit kecil ini dapat berupa fitur atau fungsi dan pengujian unit biasanya dilakukan saat kode program dibuat;
- Integration Testing ⇒ Berbeda dengan unit testing, integration testing adalah pengujian dari hasil pengabungan unit-unit yang ada di dalam software. Biasanya QA menguji bagaimana unit-unit tersebut bekerja sebagai suatu kombinasi, bukan lagi sebagai suatu unit yang individual. Integration testing sebaiknya dilakukan secara bertahap untuk menghindari kesulitan penelusuran jika terjadi kesalahan error / bug;
- Usability Testing ⇒ Usability test adalah pengujian yang dilakukan untuk memastikan apakah software sudah sesuai dengan persyaratan dari pengguna. Umumnya usability test mengevaluasi persyaratan fungsional program dan kualitas dari user interface. User berinteraksi dengan sistem untuk menentukan apakah fungsi telah seperti yang diharapkan dan apakah user interface membuat sistem dapat mudah digunakan. Pengujian ini sering dilakukan untuk mendapatkan feedback yang cepat dalam meningkatkan interface dan mengkoreksi kesalahan dalam komponen perangkat lunak;
- Performance Testing ⇒ Integration dan usability test yang menentukan apakah system dapat memenuhi kriteria kinerja berbasis waktu seperti response time atau throughput. Response time menentukan batas waktu maksimum yang diijinkan dari respon software;
- Smoke Testing ⇒ Pengujian yang akan dilakukan setelah software yang di dibuat untuk memastikan bahwa fungsi-fungsi penting dari program tersebut bekerja dengan baik. Smoke test biasanya dilakukan setiap hari atau beberapa kali per minggu;
- Stress Testing ⇒ Stress Testing adalah pengujian yang biasanya dilakukan dalam membuat sebuah website, dimana stress testing dilakukan untuk mengetahui sekuat apa server website kita menampung visitor dalam website tersebut, dengan cara melakukan hit dummy ke website menggunakan tools;
- Sanity Testing ⇒ Software testing yang akan dilakukan setelah software yang dibuat sudah hampir jadi sekaligus dengan fungsi-fungsi lengkapnya yang sudah jadi, dengan catatan bug-bug yang ditemukan pada saat smoke testing sudah berhasil di perbaiki. Tujuan dari sanity testing ini tentunya untuk memastikan bahwa bug-bug yang telah di perbaiki pada saat smoke testing sudah selesai diperbaiki dan tidak ada masalah lebih lanjut serta untuk menentukan bahwa fungsi yang diinginkan bekerja seperti yang diharapkan.
- Regression Testing ⇒ Jenis pengujian yang dilakukan saat mengembangkan software untuk mengetahui apakah fungsional sistem berjalan dengan baik. Singkatnya, tujuan utamanya yaitu untuk meminimalisir bug yang mungkin akan muncul setelah adanya pembaharuan fitur pada software.
APLIKASI YANG AKAN DI UJI COBA
Kami
akan melakukan sebuah tester aplikasi yaitu aplikasi e-voting berbasis website.
Dimana program tersebut kami buat dalam rangka memenuhi tugas akhir semester 4
dengan mata kuliah Rekayasa Perangkat Lunak, oleh sebab itu dikarenakan belum
melakukan sebuah testing yang benar maka kami memutuskan untuk melakukan
pengujian pada program yang kami buat dahulu. Untuk memenuhi tugas mata kuliah
Standar Uji Perangkat Lunak. Aplikasi ini terdapat 3 tampilan, yang pertama tampilan login, tampilan visi dan misi dan tampilan voting.
Tampilan Login
Tampilan Visi dan Misi
Tampilan Voting
Semoga artikel ini dapat membantu dalam menjawab pertanyaan-pertanyaan mengenai dasar dan tipe uji perangkat lunak. Mohon maaf bila ada kesalahan dalam penulisan. Karena kesalahan hanya milik manusia dan kebenaran hanya milik Allah swt. Terima kasih☺️
---------------------------------------------------------------------------------------------------------------------------------
Daftar Pustaka :
---------------------------------------------------------------------------------------------------------------------------------
Daftar Pustaka :
Noniisphalisa.wordpress.com. Testing dan Implementasi Perangkat Lunak https://noniisphalisa.wordpress.com/2014/12/07/testing-dan-implementasi-perangkat-lunak/
Cybermatika.blogspot.com. Dasar-dasar Pengujian Perangkat Lunak diakses melalui https://cybermatika.blogspot.com/2016/01/dasar-dasar-pengujian-perangakat-lunak.html?m=1
-----------------------------------------------------------------------------------------------------------------------------
Create by :
Farhan Muhammad Naufal
Nabila Nur Fransiska R
Dwi Suci Anggraeni
Jumat, 24 April 2020
Finite State Automata & Non Finite State Automata
Teori Bahasa dan Automata
Finite State Automata & Non Finite State
Automata
Finite
state automata adalah mesin abstrak berupa sistem model matematika dengan
masukan dan keluaran diskrit yang dapat mengenali bahasa paling sederhana
(bahasa reguler) dan dapat diimplementasikan secara nyata. Finite state
automata tidak memiliki tempat penyimpanan / memory, hanya bisa mengingat state
terkini.
Finite state automata dinyatakan oleh pasangan 5 Tuple, yaitu
:
M = (Q , Σ , δ , S , F )
Q =
Himpunan state
Σ (Sigma) =
Himpunan simbol input (alfabet)
δ (Delta) =
Fungsi transisi δ : Q × Σ
S =
State awal / initial state , S ∈ Q
F =
State akhir, F ⊆ Q
Karakteristik Finite Automata
1. Setiap
Finite Automata memiliki keadaan dan transisi yang terbatas.
2. Transisi
dari satu keadaan ke keadaan lainnya dapat bersifat deterministik atau
non-deterministik.
3. Setiap
Finite Automata selalu memiliki keadaan awal.
4. Finite
Automata dapat memiliki lebih dari satu keadaan akhir.
jika
setelah pemrosesan seluruh string, keadaan akhir dicapai, artinya otomata
menerima string tersebut.
Setiap FSA memiliki:
1.
Himpunan
berhingga (finite) status (state)
·
Satu
buah status sebagai status awal (initial state), biasa dinyatakan q0
·
Beberapa
buah status sebagai status akhir (final state).
2.
Himpunan
berhingga simbol masukan
3.
Fungsi
transisi
Menentukan status berikutnya dari setiap pasang status dan sebuah simbol
masukan.
Cara
Kerja Finite State Automata
Finite State Automata bekerja dengan cara mesin membaca memori masukan berupa
tape yaitu 1 karakter tiap saat (dari kiri ke kanan) menggunakan head baca yang
dikendalikan oleh kotak kendali state berhingga dimana pada mesin terdapat
sejumlah state berhingga.
Finite Automata selalu dalam kondisi yang disebut state awal (initial
state) pada saat Finite Automata mulai membaca tape. Perubahan state terjadi
pada mesin ketika sebuah karakter berikutnya dibaca. Ketika head telah sampai
pada akhir tape dan kondisi yang ditemui adalah state akhir, maka string yang
terdapat pada tape dikatakan diterima Finite Automata (String-string merupakan
milik bahasa bila diterima Finite Automata bahasa tersebut).
Finite State Diagram (FSD)
Finite State Automata dapat dimodelkan dengan Finite State Diagram (FSD)
dapat juga disebut State Transition Diagram. Sistem transisi adalah sistem yang
tingkah lakunya disajikan dalam bentuk keadaan-keadaan (states). Sistem
tersebut dapat bergerak dari state yang satu ke state lainnya sesuai dengan
input yang diberikan padanya.
Fungsi Transisi (δ) adalah representasi
matematis atas transisi keadaan.
Finite State Diagram terdiri dari:
·
Lingkaran
menyatakan state
Lingkaran diberi label sesuai dengan
nama state tersebut. Adapun pembagian lingkaran adalah:
·
Lingkaran
bergaris tunggal berarti state sementara
·
Lingkaran
bergaris ganda berarti state akhir
·
Anak
Panah menyatakan transisi yang terjadi.
Label di anak panah menyatakan simbol
yang membuat transisi dari 1 state ke state lain. 1 anak panah diberi label
start untuk menyatakan awal mula transisi dilakukan.
Contoh FSA : Pencek parity ganjil
Misal
input : 1101
Genap —1— Ganjil —1— Genap — 0 — Genap — 1 — Ganjil (berakhir pada ganjil) : Sehingga
“1101” diterima mesin.
Misal input : 1100
Genap — 1 — Ganjil — 1 — Genap — 0 — Genap — 0 — Genap (berakhir pada genap) : Sehingga
“1100” ditolak mesin.
Dari
contoh diatas, maka:
Q = {Genap, Ganjil}
Σ = {0,1}
S = Genap
F = {Ganjil}
atau
δ (Genap, 0) = Genap
δ (Genap, 1) = Ganjil
δ (Ganjil, 0) =
Ganjil
δ (Ganjil, 1) = Genap
FSA dibentuk dari
lingkaran yang menyatakan state:
·
Label pada lingkaran adalah nama state.
·
Busur menyatakan transisi/ perpindahan.
·
Label pada busur yaitu symbol input.
·
Lingkaran yang didahului sebuah busur tanpa label menyatakan
state awal
·
Lingkaran ganda menyatakan state akhir/ final.
Jadi sebuah mesin
otomata dapat dinyatakan dalam diagram transisi, fungsi transisi dan tabel
transisi.
Jenis Finite State Automata (FSA)
Ada dua jenis FSA :
1.
Deterministic Finite Automata (DFA)
Artinya : Dari suatu state ada tepat satu state berikutnya
untuk setiap simbol input yang diterima.
2.
Non-deterministic Finite Automata (NDFA)
/ NFA
Artinya : Dari suatu state bisa terdapat 0,1 atau lebih busur
keluar (transisi) berlabel simbol input yang sama.
Deterministic
Finite Automata (DFA)
Q = Himpunan state /
kedudukan
Σ (Sigma) = Himpunan simbol input (alfabet)
δ (Delta) = Fungsi transisi δ : Q × Σ
S = State awal / initial
state
F = State akhir / final state
Language ➝ L (M)
: ( x | δ (S,x) di dalam F)
Contoh 1 :
Pengujian
untuk menerima bit string dengan banyaknya 0 genap, serta banyaknya 1 genap.
Diagram
transisinya :
DFA nya :
Q = {q0 , q1 , q2 ,
q3}
Σ = {0,1}
S = q0
F = {q0}
Fungsi transisi :
Input : 0011
Maka tracking :
δ (q0,011) = δ (q2,11) = δ (q3,1) = q2 ⇒ Karena q2 termasuk dalam state akhir, maka “0011” berada dalam L(M)
Input : 10010
Maka tracking :
δ( q0,1010) = δ(
q1,010) = δ( q3,10) = δ( q2,0) = q0 ⇒ Karena q0 tidak termasuk dalam state
akhir, maka “10010” tidak berada dalam L(M)
Contoh 2 :
Diagram transisinya :
DFA nya :
Q = {q0 , q1 , q2}
Σ = {a,b}
S = q0
F = { q2}
Fungsi transisi :
δ( q0,a) = q0
δ( q0,b) = q1
δ( q1,a) = q1
δ( q1,b) = q2
δ( q2,a) = q1
δ( q2,b) = q2
Input : abb
Maka tracking :
δ( q0,abb) = δ( q0,bb)
= δ( q1,b) = q2 ⇒ Karena q2 termasuk dalam state akhir, maka “abb” berada
dalam L(M)
Input : baba
Maka tracking :
δ(q0,baba) = δ(q1,aba)
= δ(q1,ba) = δ(q2,a) = q1 ⇒ Karena q1 tidak termasuk dalam state akhir,
maka “baba” tidak berada dalam L(M)
Non-deterministic
Finite Automata (NDFA) / NFA
Q = Himpunan state /
kedudukan
Σ (Sigma) = Himpunan simbol input (alfabet)
δ (Delta) = Fungsi transisi, dimana δ Î Q × (Σ ∪ ε ) ➝ p(Q)
S = State awal / initial
state
F = State akhir / final state
Language ➝ L (M)
: ( x | δ (S,x) di dalam F)
Contoh :
Berikut ini sebuah contoh NFA (Q, Σ, δ, S, F) dimana : Q = {q0, q1, q2, q3, q4}
δ diberikan dalam
tabel berikut :
Σ = {a, b, c}
S = q0
F = {q4}
Sebuah kalimat di terima NFA jika:
Salah satu trackingnya berakhir di
state akhir atau himpunan state setelah membaca string tersebut mengandung
state akhir
Telusurilah, apakah kalimat-kalimat
berikut diterima NFA di atas :
ab, abc, aabc, aabb
Jawab:
δ (q0 ,ab) ⇒ δ (q0,b) ∪ δ (q1 ,b) ⇒ {q0, q2} ∪ {q1} = {q0 , q1 , q2}
Himpunan state tidak mengandung state
akhir ⇒ kalimat ab tidak diterima
δ (q0 ,abc) ⇒ δ( q0 ,bc) ∪ δ (q1 ,bc) ⇒ {δ(q0 ,c) ∪ δ(q2 ,c)} ∪ δ (q1 , c)
{{ q0 , q3 }∪{ q2 }}∪{
q1 } = {q0 , q1 , q2 ,q3 }
Himpunan state tidak mengandung state
akhir ⇒ kalimat abc tidak diterima
Ekuivalensi Antar Deterministic Finite Automata
Dua DFA M1 dan M2 dinyatakan ekivalen
apabila L(M1) = L(M2)
Reduksi
Jumlah State pada FSA
· Reduksi dilakukan untuk mengurangi jumlah state
tanpa mengurangi kemampuan untuk menerima
· State pada FSA dapat direduksi apabila terdapat useless state
· Hasil dari FSA yang direduksi merupakan
ekivalensi dari FSA semula
Pasangan
State dapat dikelompokkan berdasarkan:
· Distinguishable State (dapat
dibedakan)
Dua state p dan q dari suatu DFA
dikatakan indistinguishable apabila:
δ
(q,w) Î F dan δ (p,w) Î
F atau δ (q,w) ∉ F dan δ (p,w) ∉
F untuk semua w Î S*
· Indistinguishable State (tidak dapat dibedakan)
Dua state p dan q dari suatu DFA
dikatakan distinguishable jika ada
string w Î
S* hingga:
δ
(q,w) Î F dan δ (p,w) ∉ F
Reduksi Jumlah State pada FSA - Relasi
Pasangan dua buah state memiliki salah
satu kemungkinan : distinguishable
atau indistinguishable tetapi tidak
kedua-duanya. Dalam hal ini terdapat sebuah relasi :
jika p
dan q indistinguishable,
dan q dan r
indistinguishable
maka p, r indistinguishable dan
p, q, r indistinguishable
Dalam melakukan eveluasi state, didefinisikan
suatu relasi : Untuk Q yg merupakan himpunan semua state
·
D adalah
himpunan state-state distinguishable, dimana D Ì Q
·
N adalah himpunan state-state indistinguishable, dimana N Ì Q
·
maka x Î N jika x Î Q dan x Ï D
Reduksi Jumlah State pada FSA – Step
· Hapuslah semua state yang tidak dapat dicapai dari
state awal (useless state)
· Buatlah semua pasangan state (p, q) yang distinguishable, dimana p Î F
dan q Ï
F. Catat semua pasangan-pasangan state tersebut.
· Cari state lain yang distinguishable dengan aturan :
“Untuk semua (p, q) dan semua a Î ∑,
hitunglah δ (p, a) = pa dan
δ (q, a) = qa
Jika pasangan (pa, qa) adalah pasangan state yang distinguishable
maka pasangan (p, q) juga termasuk pasangan yang distinguishable.
· Semua pasangan state yang tidak termasuk sebagai
state yang distinguishable merupakan state-state
indistinguishable
· Beberapa state yang indistinguishable dapat digabungkan menjadi satu state.
· Sesuaikan transisi dari state-state gabungan
tersebut.
Contoh :
Sebuah Mesin DFA
·
State q5 tidak dapat dicapai dari state awal
dengan jalan apapun (useless state). Hapus
state q5
·
Catat state-state distinguishable, yaitu :
q4 Î F sedang q0, q1, q2, q3 Ï F
sehingga pasangan
(q0, q4) (q1, q4) (q2, q4) dan (q3, q4)
adalah distinguishable.
· Pasangan-pasangan state lain yang distinguishable diturunkan berdasarkan
pasangan dari langkah 2, yaitu :
- Untuk pasangan (q0, q1)
δ(q0, 0) = q1 dan δ(q1, 0) = q2 ➝ belum
teridentifikasi
δ(q0, 1) = q3 dan δ(q1, 1) = q4 ➝
(q3, q4) distinguishable
maka (q0, q1) adalah distinguishable.
- Untuk pasangan (q0, q2)
δ (q0, 0) = q1 dan δ(q2, 0) = q1 ➝
belum teridentifikasi
δ(q0, 1) = q3 dan δ(q2, 1) = q4 ➝
(q3, q4) distinguishable
maka (q0, q2) adalah distinguishable
· Setelah diperiksa semua pasangan state maka
terdapat state-state yang distinguishable
: (q0, q1), (q0, q2), (q0, q3), (q0, q4), (q1, q4), (q2, q4), (q3, q4)
Karena berdasarkan relasi-relasi yang ada,
tidak dapat dibuktikan (q1, q2), (q1, q3) dan (q2, q3) distinguishable, sehingga disimpulkan pasangan-pasangan state
tersebut indistinguishable.
· Karena q1 indistinguishable
dengan q2, q2 indistinguishable dengan q3, maka dapat disimpulkan q1, q2, q3
saling indistinguishable dan dapat dijadikan
satu state.
· Berdasarkan hasil diatas maka hasil dari DFA yang direduksi menjadi :
Semoga artikel ini
dapat membantu dalam memahami tentang Finite State Automata & Non Finite State
Automata. Mohon maaf bila ada salah penulisan. Karena kesalahan hanya milik
manusia dan kebenaran hanya milik Allah SWT. Terima kasih ☺️
Daftar Pustaka :
Materi 7 Finite
State Automata & Non Finite State Automata Dosen pengampu Teori Bahasa dan Automata : Garno, M.Kom Fakultas Ilmu Komputer Universitas Singaperbangsa Karawang.
riskasimaremare.wordpress.com. Finite State Automata diakses melalui
docplayer.info. Teori Bahasa dan Automata Finite State Automata & Non Finite State Automata. Diakses melalui https://docplayer.info/36555908-Teori-bahasa-dan-automata-finite-state-automata-non-finite-state-automata.html
Langganan:
Postingan (Atom)