Studi Kasus
Perhatikan gambar NFA ε-move berikut:
Kita akan coba merubah diagram ini ke NDFA tanpa ε-move dengan tahapan yang sudah diberikan pada materi sebelumnya.
Langkah 1
Menentukan tabel transisi, kebetulan sudah di gambarkan pada gambar diatas
Langkah 2
Menentukan ε-closure untuk setiap state:
Langkah 3
Carilah setiap fungsi transisi hasil perubahan dari NDFA ε-move ke NDFA tanpa ε-move rumus:
δ'(state,input) = ε-closure (δ(ε-closure (state),input))
Langkah 4
Berdasarkan hasil diatas maka kita bisa membuat tabel transisi untuk NFA tanpa ε-move:
Langkah 5
Tentukan state-state akhir untuk NDFA tanpa ε-move tersebut yaitu state-state akhir semula ditambah dengan state-state yang ε-closure nya menuju ke salah satu dari state akhir semula.
Himpunan state akhir semula adalah q0. State-state yang ε-closure nya menuju q0, kita lihat
ε-cl (q2) = {q0,q1,q2} ini yang mengandung q0
Sehingga himpunan state akhirnya adalah {q0,q2).
Berikut gambar hasil NFA tanpa ε-move yang ekivalen:
Penggabungan dan Konkatenasi
Pada mesin Finite Automata kita dapat melakukan penggabungan, disebut Union serta Konkatenasi.
Misal terdapat 2 mesin sebagai berikut:
Bila diketahui:
L(M1) adalah bahasa yang diterima oleh M1.
L(M2) adalah bahasa yang diterima oleh M2.
Dilakukan operasi union berikut:
L(M3) = L(M1) ∪ L(M2) atau dengan notasi lain:
L(M3) = L(M1) + L(M2)
Kita bisa membuat penggabungan atau disini kita sebut mesin M3 yang menerima bahasa L(M3) dengan cara:
- Tambahkan state awal untuk M3, hubungkan dengan state awal M1 dan state awal M2 dengan transisi ε.
- Tambahkan sate akhir untuk M3 hubungkan dengan state-state akhir M1 dan state-state akhir M2 menggunakan transisi ε.
Berikut hasil penggabungan dari M1 dan M2 menjadi M3
Kemudian kita lanjutkan untuk menentukan konkatenasi atau disini disebut L(M4) = L(M1) L(M2) dengan cara:
1. State awal M1 menjadi state awal M4
2. State akhir M2 menjadi state akhir M4
3. Hubungkan state-state akhir M1 dengan sate awl M2 menggunakan transisi ε.
