Assalamualaikum Wr. Wb.
Nama : Muhammad Diki Hendriyanto
Kelas : 4G
NPM : 1810631170199
Pada postingan kali ini saya akan membahas materi mengenai penerapan FSA(Finite State Automata), DFA(Deterministic Finite Automata), NFA(Non Deterministic Finite Automata), Ekuivalen antar DFA, dan juga Reduksi Jumlah State.
1. PENERAPAN FSA
Finite State Automata
FSA adalah model matematika suatu sistem yang menerima input dan output diskrit. FSA juga merupakan mesin automata dari suatu bahasa regular. FSA juga tidak memiliki tempat penyimpanan sehingga kemampuan mengingat terbatas (contoh: elevator/lift). Dalam FSA juga dikenal himpunan state-state tertentu yang disebut sabagai FINAL STATE. Perubahan dari satu state ke state berikutnya mengikuti sturan tertentu yang dirumuskan sebagai suatu FUNGSI transisi M.
FSA didefinisikan sebagai pasangan 5 Tupel → M = (Q, ∑, δ, S, F).
Keterangan :
Q : Himpunan hingga state.
∑ (Sigma) : Himpunan hingga simbol input (alfabet).
δ (Delta) : Fungsi transisi, menggambarkan transisi state FSA akibat pembacaan simbol input. Biasanya fungsi transisi ini digambarkan dalam bentuk tabel.
S ∈ : State awal.
F ⊆ : Himpunan state akhir.
Contoh :
Buatlah diagram transisi dari FSA yang didefinisikan sebagai :
M = (K, VT, M, S, Z) dimana :
S ={S0, S1, S2, S3}
VT ={ 0,1 }
K ={S0 , S3}
Dengan fungsi transisi M ada pada tabel transisi sebagai berikut :
FSA terbagi menjadi dua jenis, yaitu :
1. Deterministic Finite Automata
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.
2. DFA (DETERMINISTIC FINITE AUTOMATA)
Deterministic Finite Automata (DFA) → M = (Q, ∑, δ, S, F), dimana :
Q : Himpunan state/kedudukan
∑ (Sigma) : Himpunan simbol input
δ (Delta) : Fungsi transisi, dimana δ ∈ Q x ∑ → Q
S ∈ : State awal (initial state)
F ⊆ : Himpunan state akhir (final state)
Language → L(M) : (x | δ (S,x) di dalam F)
Pada DFA, untuk karakter input tertentu, mesin hanya menuju satu state. Fungsi transisi didefinisikan pada setiap state untuk setiap simbol input. Dan juga di DFA null (atau ε) pemindahan tidak diizinkan, DFA tidak dapat mengubah state tanpa karakter input apa pun.
Contoh :
Diketahui DFA :
Q = {q0, q1, q2}
∑ = {a, b}
S = q0
F = {q0, q1}
δ diberikan dalam tabel berikut :
3. NDFA/NFA (NON DETERMINISTIC FINITE AUTOMATA)
Non Deterministic Finite Automata (NFA) → M = (Q, ∑, δ, S, F), dimana :
Q : Himpunan state/kedudukan
∑ (Sigma) : Himpunan simbol input
δ (Delta) : Fungsi transisi, dimana δ ∈ Q x (∑ ⋃ ε) → P(Q)
P(Q) : set of all subsets of Q
S ∈ : State awal (initial state)
F ⊆ : Himpunan 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}
∑= {a, b,c}
S = q0
F = {q4}
δ diberikan dalam tabel berikut :
Digram Transisi yang dapat dibuat :
L(M) = {aabb,...}
Sebuah kalimat di terima NFA jika :
Salah satu tracing-nya berakhir di state akhir, atau himpunan state setelah membaca string tersebut mengandung state akhir.
Penelusuran/Tracing :
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
δ(q0, aabc) ⇒ δ(q0, abc) ∪ δ(q1, abc) ⇒ {δ(q0, bc) ∪ δ(q1, bc)} ∪ δ(q1, bc)
⇒ {{δ(q0, c) ∪ δ(q2, c)} ∪ δ(q1, c)} ∪ δ(q2, c)
⇒ {{{q0, q3} ∪ {q2}} ∪ {q1}} ∪ {q1} = {q0, q1, q2, q3}
Himpunan state tidak mengandung state akhir ⇒ kalimat aabc tidak diterima
δ(q0, aabb) ⇒ δ(q0,abb) ∪ δ(q1, abb) ⇒ {δ(q0, bb) ∪ δ(q1, bb)} ∪ δ(q1, bb)
⇒ {{δ(q0, b) ∪ δ(q2, b)} ∪ δ(q1, b)} ∪ δ(q1, b)
⇒ {{{q0, q2} ∪ {q2, q4}} ∪ {q1}} ∪ {q1} = {q0, q1, q2, q4}
Himpunan state mengandung state akhir ⇒ kalimat aabb diterima
4. EKUIVALEN ANTAR DFA
Dua buah DFA dikatakan equivalen jika keduanya dapat menerima bahasa yang sama. Misalkan kedua DFA tersebut adalah A dan A’. Misalkan pula bahasa yang diterima adalah bahasa L yang dibangun oleh alfabet VT = {a1, a2, a3, ..., an}. Berikut ini algoritma untuk menguji equivalensi dua buah DFA.
Contoh :
Jawab :
Dengan menggunakan algoritma di atas maka dapat dibentuk tabel berikut,
5. REDUKSI JUMLAH STATE
Reduksi dilakukan untuk mengurangi jumlah state tanpa mengurangi kemampuan untuk menerima suatu bahasa seperti semula (efisiensi). State pada FSA dapat direduksi apabila terdapat useless state. Hasil dari FSA yang direduksi merupakan ekuivalensi dari FSA semula.
Pasangan State dapat dikelompokkan berdasarkan:
1. Distinguishable State yang artinya 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 δ(q,w) ∉ F
2. Indistinguishable State yang artinya tidak dapat dibedakan.
Dua state p dan q dari suatu DFA dikatakan distinguishable apabila :
Ada string w ∈ S* hingga
δ(q,w) ∈ F dan δ(p,w) ∉ F
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
Langkah :
Contoh :
Lakukan Reduksi State pada DFA di atas?
Jawab :
Langkah :
1. State q5 tidak dapat dicapai dari state awal dengan jalan apapun (useless state). Hapus state q5.
2. 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.
3. Pasangan-pasangan state lain yang distinguishable diturunkan berdasarkan pasangan dari langkah kedua, 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.
4. 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.
5. Karena q1 indistinguishable dengan q2, q2 indistinguishable dengan q3, maka dapat disimpulkan q1, q2, q3 saling indistinguishable dan dapat dijadikan satu state.
DAFTAR PUSTAKA
Materi 7 Finite State Automata & Non Finite State Automata [pdf]. Dosen Pengampu: Garno, M.Kom. Fakultas Ilmu Komputer, Universitas Singaperbangsa Karawang.
https://socs.binus.ac.id/2019/12/21/teknik-kompilasi-perbedaan-dfa-dan-nfa/
https://www.geeksforgeeks.org/introduction-of-finite-automata/
https://www.slideshare.net/BantaCut/teori-bahasadanotomata
https://www.scribd.com/doc/179155911/Reduksi-jumlah-state-pada-DFA
Keterangan :
Q : Himpunan hingga state.
∑ (Sigma) : Himpunan hingga simbol input (alfabet).
δ (Delta) : Fungsi transisi, menggambarkan transisi state FSA akibat pembacaan simbol input. Biasanya fungsi transisi ini digambarkan dalam bentuk tabel.
S ∈ : State awal.
F ⊆ : Himpunan state akhir.
Contoh :
Buatlah diagram transisi dari FSA yang didefinisikan sebagai :
M = (K, VT, M, S, Z) dimana :
S ={S0, S1, S2, S3}
VT ={ 0,1 }
K ={S0 , S3}
Dengan fungsi transisi M ada pada tabel transisi sebagai berikut :
Diagram Transisi :
Cara kerja FSA :
Mula-mula dalam state S0
Jika dari S0 menerima 1 : akan ke State-S1
Jika dari S0 menerima 11 : akan ke State-S1 lalu ke S2
Jika dari S0 menerima 0 : akan tetap di State- S0
Jika dari S0 menerima 10 : akan tetap kembali lagi State- S0
Jika dari S0 berturut-turut menerima masukan : 111, maka ia akan kembali ke- S0
FSA Sebagai Pengenal String
Mesin FSA tersebut jika menerima masukan sederetan simbol dari simbol-simbol yang diijinkan maka akan menuju suatu state tertentu. Jika state akhir yang ditempuh setelah suatu FSA menerima sederetan simbol adalah state final, maka deretan simbol (string) tersebut dikatakan dikenali oleh FSA, atau dengan kata lain FSA mengenali string tersebut.
String yang dikenali oleh FSA merupakan suatu bahasa yang dikenali oleh FSA tersebut. Jika dimiliki FSA M maka bahasa yang dikenali oleh FSA di notasikan sebagai :
L(M) = { x | x semua string yang mengantar M dari S0 ke (Si ϵ Z) }
Untuk mesin FSA pada contoh :
L(M) = { 0* , 0*(10)0* , 0*(110,111)0* }
Contoh :
Tentukan bahasa L(M) yang dikenali oleh Mesin M berikut ini :
Jawab :
- Dari diagram terlihat bahwa final-state adalah S3. Pergerakan state yang mengantar ke final state adalah S0 S1 S2 S3 yakni string : 011 atau string 111 yang dapat ditulis sebagai (0,1)11.
- Pergerakan yang lain adalah dari S0 langsung ke S2 yaitu : S0 S2 S3 yang dilakukan melalui string : 01 Setelah berada pada final state masih ada pergerakan yang bersifat rekursif pada S3 yaitu apabila diberikan masukan 0,00,000,… atau : 0*.
- Dengan demikian jika seluruh string tersebut digabungkan akan menjadi : (0,1)110* U 010*, sehingga bahasa yang dikenali adalah : L(M)= { (0,1)110* U 010* } = { ((0,1)11 U 01)0* }
1. Deterministic Finite Automata
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.
2. DFA (DETERMINISTIC FINITE AUTOMATA)
Deterministic Finite Automata (DFA) → M = (Q, ∑, δ, S, F), dimana :
Q : Himpunan state/kedudukan
∑ (Sigma) : Himpunan simbol input
δ (Delta) : Fungsi transisi, dimana δ ∈ Q x ∑ → Q
S ∈ : State awal (initial state)
F ⊆ : Himpunan state akhir (final state)
Language → L(M) : (x | δ (S,x) di dalam F)
Pada DFA, untuk karakter input tertentu, mesin hanya menuju satu state. Fungsi transisi didefinisikan pada setiap state untuk setiap simbol input. Dan juga di DFA null (atau ε) pemindahan tidak diizinkan, DFA tidak dapat mengubah state tanpa karakter input apa pun.
Contoh :
Diketahui DFA :
Q = {q0, q1, q2}
∑ = {a, b}
S = q0
F = {q0, q1}
δ diberikan dalam tabel berikut :
Ilustrasi graf untuk DFA F sebagai berikut :
Penelusuran/Tracing :
Telusurilah, apakah kalimat-kalimat berikut diterima DFA : abababaa, aaaabab, aaabbaba.
Jawab :
M(q0,abababaa) → M(q0,bababaa) → M(q1,ababaa) → M(q0,babaa) → M(q1,abaa) → M(q0,baa) → M(q1,aa) → M(q0,a) → q0
Tracing berakhir di q0 (stata penerima) → kalimat abababaa diterima
M(q0,aaaabab) → M(q0,aaabab) → M(q0,aabab) → M(q0,abab) → M(q0,bab) → M(q1,ab) → M(q0,b) → q1
Tracing berakhir di q1 (stata penerima) → kalimat aaaababa diterima
M(q0,aaabbaba) → M(q0,aabbaba) → M(q0,abbaba) → M(q0,bbaba)→ M(q1,bbaba) → M(q2,baba) → M(q2,aba) → M(q2,ba) → M(q2,a) → q2
Tracing berakhir di q2 (bukan stata penerima) --> kalimat aaabbaba ditolak
Kesimpulan : Sebuah kalimat diterima oleh DFA di atas jika tracingnya berakhir di salah satu state akhir.
3. NDFA/NFA (NON DETERMINISTIC FINITE AUTOMATA)
Non Deterministic Finite Automata (NFA) → M = (Q, ∑, δ, S, F), dimana :
Q : Himpunan state/kedudukan
∑ (Sigma) : Himpunan simbol input
δ (Delta) : Fungsi transisi, dimana δ ∈ Q x (∑ ⋃ ε) → P(Q)
P(Q) : set of all subsets of Q
S ∈ : State awal (initial state)
F ⊆ : Himpunan 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}
∑= {a, b,c}
S = q0
F = {q4}
δ diberikan dalam tabel berikut :
Sebuah kalimat di terima NFA jika :
Salah satu tracing-nya berakhir di state akhir, atau himpunan state setelah membaca string tersebut mengandung state akhir.
Penelusuran/Tracing :
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
δ(q0, aabc) ⇒ δ(q0, abc) ∪ δ(q1, abc) ⇒ {δ(q0, bc) ∪ δ(q1, bc)} ∪ δ(q1, bc)
⇒ {{δ(q0, c) ∪ δ(q2, c)} ∪ δ(q1, c)} ∪ δ(q2, c)
⇒ {{{q0, q3} ∪ {q2}} ∪ {q1}} ∪ {q1} = {q0, q1, q2, q3}
Himpunan state tidak mengandung state akhir ⇒ kalimat aabc tidak diterima
δ(q0, aabb) ⇒ δ(q0,abb) ∪ δ(q1, abb) ⇒ {δ(q0, bb) ∪ δ(q1, bb)} ∪ δ(q1, bb)
⇒ {{δ(q0, b) ∪ δ(q2, b)} ∪ δ(q1, b)} ∪ δ(q1, b)
⇒ {{{q0, q2} ∪ {q2, q4}} ∪ {q1}} ∪ {q1} = {q0, q1, q2, q4}
Himpunan state mengandung state akhir ⇒ kalimat aabb diterima
4. EKUIVALEN ANTAR DFA
Dua buah DFA dikatakan equivalen jika keduanya dapat menerima bahasa yang sama. Misalkan kedua DFA tersebut adalah A dan A’. Misalkan pula bahasa yang diterima adalah bahasa L yang dibangun oleh alfabet VT = {a1, a2, a3, ..., an}. Berikut ini algoritma untuk menguji equivalensi dua buah DFA.
- 1) Berikan nama kepada semua stata masing-masing DFA dengan nama berbeda. Misalkan nama nama tersebut adalah : S, A1, A2, ... untuk DFA A, dan : S’, A1’, A2’, ... untuk DFA A’.
- 2) Buat tabel (n+1) kolom, yaitu kolom-kolom : (v, v’), (va1, va1’), ..., (van, van’), yaitu pasangan terurut (stata DFA A, stata DFA A’).
- 3) Isikan (S, S’) pada baris pertama kolom (v, v’), dimana S dan S’ masing-masing adalah stata awal masing-masing DFA.
- 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 (va1, va1’) Lakukan hal yang sama untuk kolom-kolom berikutnya.
- 5) Perhatikan nilai-nilai pasangan terurut pada baris pertama. Jika terdapat nilai pasangan terurut pada kolom (va1, va1’) s/d (van, van’) 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 DFA 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 DFA tersebut ekuivalen.
Contoh :
Periksalah ekuivalensi kedua DFA berikut :
Dengan menggunakan algoritma di atas maka dapat dibentuk tabel berikut,
Keterangan :
> (2, 5) adalah pasangan terurut baru
> (3, 6) adalah pasangan terurut baru
> (4, 7) adalah pasangan terurut baru
> tidak ada lagi pasangan terurut baru
5. REDUKSI JUMLAH STATE
Reduksi dilakukan untuk mengurangi jumlah state tanpa mengurangi kemampuan untuk menerima suatu bahasa seperti semula (efisiensi). State pada FSA dapat direduksi apabila terdapat useless state. Hasil dari FSA yang direduksi merupakan ekuivalensi dari FSA semula.
Pasangan State dapat dikelompokkan berdasarkan:
1. Distinguishable State yang artinya 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 δ(q,w) ∉ F
2. Indistinguishable State yang artinya tidak dapat dibedakan.
Dua state p dan q dari suatu DFA dikatakan distinguishable apabila :
Ada string w ∈ S* hingga
δ(q,w) ∈ F dan δ(p,w) ∉ F
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
Langkah :
- Hapuslah semua state yg 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 merupakanstate-state indistinguishable.
- Beberapa state yang indistinguishable dapat digabungkan menjadi satu state.
- Sesuaikan transisi dari state-state gabungan tersebut.
Contoh :
Sebuah Mesin DFA
Lakukan Reduksi State pada DFA di atas?
Jawab :
Langkah :
1. State q5 tidak dapat dicapai dari state awal dengan jalan apapun (useless state). Hapus state q5.
2. 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.
3. Pasangan-pasangan state lain yang distinguishable diturunkan berdasarkan pasangan dari langkah kedua, 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.
4. 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.
5. Karena q1 indistinguishable dengan q2, q2 indistinguishable dengan q3, maka dapat disimpulkan q1, q2, q3 saling indistinguishable dan dapat dijadikan satu state.
6. Berdasarkan hasil diatas makahasil dari DFA yang direduksi menjadi :
Sekian pembahasan materi dalam postingan kali ini, mohon maaf apabila ada kekurangan, semoga materi di atas dapat bermanfaat. Akhir kata terima kasih.
Wassalamualaikum Wr. Wb.
DAFTAR PUSTAKA
Materi 7 Finite State Automata & Non Finite State Automata [pdf]. Dosen Pengampu: Garno, M.Kom. Fakultas Ilmu Komputer, Universitas Singaperbangsa Karawang.
https://socs.binus.ac.id/2019/12/21/teknik-kompilasi-perbedaan-dfa-dan-nfa/
https://www.geeksforgeeks.org/introduction-of-finite-automata/
https://www.slideshare.net/BantaCut/teori-bahasadanotomata
https://www.scribd.com/doc/179155911/Reduksi-jumlah-state-pada-DFA
EmoticonEmoticon