Penerapan FSA, DFA(Deterministik Finite Automata), NFA(non deterministik Finite Automata), Ekuivalen antar DFA, Reduksi Jumlah State

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 (FSA) adalah model matematika yang dapat menerima input dan mengeluarkan output yang memiliki state yang berhingga banyaknya dan dapat berpindah dari satu state ke state lainnya berdasarkan input dan fungsi transisi. 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 (Finite state automata) 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).

Contoh  :

Pencek parity ganjil

Misal input : 1101
Genap 1 Ganjil 1 Genap 0 Genap 1 Ganjil : diterima mesin
Misal input : 1100
Genap 1 Ganjil 1 Genap 0 Genap 0 Genap : 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

Sebuah FSA (Finite state automata) 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
• Lingkaranb ganda menyatakan state akhir/ final.
Jadi sebuah mesin otomata dapat dinyatakan dalam diagram transisi, fungsi transisi dan tabel transisi.

Ada dua jenis FSA :

Finite State Automata dapat berupa:

1. Deterministic Finite Automata (DFA) adalah dari suatu state ada tepat satu state berikutnya untuk setiap simbol masukan yang diterima. Deterministik artinya tertentu/sudah tertentu fungsi transisinya.

Deterministic finite automata (DFA)  -> M = (Q, ∑, δ, S, F), Notasi matematis DFA dimana:
Q  : himpunan state/kedudukan

∑  : himpunan simbol input

∂   : 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)

Contoh 1:

Diketahui DFA :

Q = {q0, q1, q2}  δ diberikan dalam tabel berikut :

∑= {a, b} S = q0

F = {q0, q1}

L(M) = {abababaa, aaaabab,aabababa,…}

Penelusuran/Tracking:

Telusurilah, apakah kalimat-kalimat berikut diterima DFA di atas: abababaa,  aaaabab , aaabbaba Jawab :

δ (q0,abababaa)  ⇒ δ (q0,bababaa) ⇒ δ (q1,ababaa) ⇒ δ (q0,babaa) ⇒ δ (q1,abaa) ⇒ δ (q0,baa) ⇒ δ (q1,aa) ⇒ δ (q0,a) ⇒ q0

Tracking berakhir di q0 (state AKHIR) ⇒ kalimat abababaa diterima

Kesimpulan :

Sebuah kalimat diterima oleh DFA di atas jika tracingnya berakhir di salah satu state AKHIR.

Contoh 2 :

Pengujian untuk menerima bit string dengan banyaknya 0 genap, serta banyaknya 1 genap.
0011 : diterima
10010 : ditolak, karena banyaknya 0 ganjil
Diagram transisi-nya :

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

fungsi transisi adalah:

δ( q0,011) = δ( q2,11) = δ( q3,1) = q2 è Ditolak
δ( q0,1010) = δ( q1,010) = δ( q3,10) = δ( q2,0) = q0 è Diterima.

2. Non-deterministic Finite Automata (NFA) adalah dari suatu state ada 0, 1 atau lebih state berikutnya untuk setiap simbol masukan yang diterima.

Non Deterministic finite automata (NFA)  -> M = (Q, ∑, δ, S, F), dimana :

Q  : himpunan state/kedudukan

∑  : himpunan simbol input

∂   : 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)

Non-Deterministic Finite Automata:

• Otomata berhingga yang tidak pasti untuk setiap pasangan state input, bisa memiliki 0 (nol) atau lebih pilihan untuk state berikutnya.
• Untuk setiap state tidak selalu tepat ada satu state berikutnya untuk setiap simbol input yang ada.
• Dari suatu state bisa terdapat 0,1 atau lebih busur keluar (transisi)
berlabel simbol input yang sama.
• Untuk NFA harus dicoba semua kemungkinan yang ada sampai
terdapat satu yang mencapai state akhir.
• Suatu string x dinyatakan diterima oleh bahasa NFA, M= (Q, _, d, S, F) bila {x | d (S,x) memuat sebuah state di dalam F}

Kedua finite automata di atas mampu mengenali himpunan reguler secara presisi. Dengan demikian kedua finite automata itu dapat mengenali string-string yang ditunjukkan dengan ekspresi reguler secara tepat.

DFA dapat menuntun recognizer(pengenal) lebih cepat dibanding NDFA. Namun demikian, DFA berukuran lebih besar dibanding NDFA yang ekivalen dengannya. Lebih mudah membangun NDFA dibanding DFA untuk suatu bahasa, namun lebih mudah mengimplementasikan DFA dibanding NDFA.

Contoh :

Berikut ini sebuah contoh NFA (Q, ∑, δ, S, F). dimana : Q = {q 0, q1 , q2 ,q3 , q4 }

δ diberikan dalam table berikut :

∑= {a, b,c}

S =  q0

F = {q4}

∑= {a, b,c}

S =  q0

F = {q4 }

Sebuah kalimat di terima NFA jika:

Salah satu tracking-nya 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

Untuk suatu bahasa regular, kemungkinan ada sejumlah Deterministic Finite Automata yang dapat menerimanya. Perbedaannya hanyalah jumlah state yang dimiliki otomata-otomata yang saling ekuivalen tersebut. Tentu saja, dengan alasan kepraktisan, kita memilih otomata dengan jumlah state yang lebih sedikit.

Sasaran kita di sini adalah mengurangi jumlah state dari suatu Finite State Automata, dengan tidak mengurangi kemampuannya semula untuk menerima suatu bahasa.

Ada dua buah istilah baru yang perlu kita ketahui yaitu :

1. Distinguishable yang berarti dapat dibedakan.

2. Indistinguishable yang berarti tidak dapat dibedakan.

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 suatu bahasa seperti semula (efisiensi). State pada FSA dapat direduksi apabila terdapat useless state. Hasil dari FSA yang direduksi merupakan ekivalensi dari FSA semula

Pasangan State dapat dikelompokkan berdasarkan:

1. 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) ∉ 

                 untuk semua w Î S*

2. 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 adalah 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

Langkah - langkah untuk melakukan reduksi ini adalah :

1. Hapuslah semua state yg tidak dapat dicapai dari state awal  (useless state)

2. 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.

Reduksi Jumlah State Pada FSA 

Contoh :

Sebuah Mesin DFA

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 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.

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  maka hasil dari DFA yang direduksi menjadi:

Daftar Pustaka :

https://hennyhalimah.blogspot.com/search?updated-max=2017-07-07T08:11:00-07:00&max-results=7

Tata Bahasa Bebas Konteks POHON PENURUNAN

Hirarki Chomsky

Tata bahasa ( grammar ) bisa didefinisikan secara formal sebagai kumpulan dari himpunan-himpunan variabel, simbol-simbol terminal, simbol awal, yang dibatasi oleh aturan-aturan produksi. Pada tahun 1959, seorang ahli bernama Noam Chomsky melakukan penggolongan tingkatan bahasa menjadi empat, yang disebut dengan hirarki Chomsky. Penggolongan tersebut bisa dilihat pada tabel berikut.

Tata Bahasa Bebas Konteks (Context Free Grammar/CFG)

Bahasa bebas konteks menjadi dasar dalam pembentukan suatu parser/proses analisis sintaksis.

Bagian sintaks dalam suatu kompilator kebanyakan didefinisikan dalam tata bahasa bebas konteks.

Context Free Grammar (CFG)/ Bahasa Bebas Konteks adalah sebuah tata bahasa dimana tidak terdapat pembatasan pada hasil produksinya, Contoh Pada aturan produksi :

α → β

batasannya hanyalah ruas kiri (α) adalah sebuah simbol variabel. Sedangkan contoh aturan produksi yang termasuk CFG adalah seperti di bawah :

B → CDeFg

 D → BcDe

Context Free Grammar ( CFG ) adalah tata bahasa yang mempunyai tujuan sama seperti halnya tata bahasa regular yaitu merupakan suatu cara untuk menunjukkan bagaimana menghasilkan suatu untai-untai dalam sebuah bahasa.

Parsing

• Sebuah pohon (tree) adalah : suatu graph terhubung tidak sirkuler, yang memiliki satu simpul (node) /vertex yang disebut akar (root) dan dari root memiliki lintasan ke setiap simpul.
• Poh on penurunan (derivation tree/parse tree) berguna untuk menggambarkan bagaimana memperoleh suatu string (untai) dengan cara menurunkan simbol-simbol non terminal. Setiap simbol variabel akan diturunkan menjadi terminal, sampai tidak ada yang belum tergantikan.

Contoh 1

S -> AA

A-> AAA | a | bA | Ab

Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan “bbabaaba”

Akan kita gambarkan pohon penurunan untuk memperoleh untai : “bbabaaba”

Gambar 1. Pohon Penurunan untuk untai “bbabaaba”

-          - Pada pohon tersebut simbol awal akan menjadi akar (root).

-          - Setiap kali penurunan dipilih aturan produksi  yang menuju solusi.

-          - Simbol-simbol variabel (huruf besar) akan menjadi simpul-simpul yang mempunyai anak.

-          - Simpul-simpul yang tidak mempunyai anak akan menjadi symbol terminal (huruf kecil)

-          - Kalau kita baca simbol terminal yang ada pada gambar 1 dari kiri ke kanan akan diperoleh untai          “bbabaaba”.

Contoh 2

S -> AB

A -> Aa | bB

B -> a | Sb

Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan “baabaab”

Akan kita gambarkan pohon penurunan untuk memperoleh untai : “baabaab”

Gambar 2. Pohon Penurunan untuk untai : “baabaab”

-          - Pada pohon tersebut simbol awal akan menjadi akar (root).

-          - Setiap kali penurunan dipilih aturan produksi  yang menuju solusi.

-          -  Simbol-simbol variable (huruf besar) akan menjadi simpul-simpul yang m empunyai anak.

-          - Simpul-simpul yang tidak mempunyai anak akan menjadi symbol terminal (huruf kecil).

-          - Kalau kita baca simbol terminal yang ada pada gambar 1 dari kiri ke kanan akan diperoleh

        untai“baabaab”.

Contoh 3

S-> Ba | Ab

A -> Sa | Aab | a

B -> Sb | Bba | b

Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan “bbaaaabb”

Akan kita gambarkan pohon penurunan untuk memperoleh untai : “bbaaaabb”

Gambar 3. Pohon Penurunan untuk untai : “bbaaaabb”

-       -   Biasanya persoalan yang diberikan berkaitan dengan pohon penurunan adalah untuk mencari              penurunan yang hasilnya menuju pada suatu untai yang ditentukan.

     -  Dalam hal ini, perlu untuk melakukan percobaan pemilihan aturan produksi yang bisa menuju ke solusi.

Ambiguitas

Ambiguitas/ke-dwi adalah terjadi bila terdapat lebih dari satu pohon penurunan yang berbeda untuk memperoleh suatu string/untai.

Contoh 1

S -> AB | C

A -> aAb  | ab

B -> cBd  | cd

C -> aCd  | aDd

D -> bDc  | bc

Buatlah pohon penurunan dari himpunan produksi diatas untuk membangkitkan string dengan susunan “aabbccdd”

Pohon penurunan untaian : “aabbccdd” (1)

Pohon penurunan untaian : “aabbccdd” (2)

-    Kita bisa melihat bahwa untuk untai yang sama (“aabbccdd”) dapat dibuat pohon penurunan yang berbeda, maka bahwa dapat dikatakan tata bahasa bebas konteks tersebut ambiguitas.

-   Jadi, untuk menunjukan bahwa suatu tata bahasa bebas konteks ambigu, bisa dilakukan dengan menemukan untai yang memungkinkan pembentukan lebih dari satu pohon penurunan.

-    Ambiguitas dapat menimbulkan masalah pada bahasa-bahasa tertentu, baik bahasa alami maupun pada bahasa pemrograman.

-  Bila suatu struktur bahasa memiliki lebih dari suatu dekomposisi (penurunan), dan susunannya akan menentukan arti, maka artinya menjadi ambigutas.

Berikut ini video penjelasan dari Latihan soal diatas :

Teknik-Teknik Penyederhanaan Produksi Empty,Unit dan Useless

PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS

Sebuah bahasa formal adalah abstraksi terdiri dari himpunan simbol-simbol dan aturan-aturan yang mana simbol-simbol tersebut bisa dikombinasikan kedalam entitas yang disebut kalimat.

Bahasa adalah himpunan string-string dari simbol-simbol untuk suatu alphabet atau rangkaian simbol-simbol yang mempunyai makna.Bahasa Kosong adalah bahasa yang tidak terdiri dari string-string, dinotasikan dengan ->. Bahasa kosong berbeda dengan bahasa yang terdiri dari string kosong {ε}.

Melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tidak perlu atau aturan produksi yang tidak berarti. contoh Penyederhanaan tata bahasa dalam Teori bahasa dan Otomata,berikut adalah :

Tujuan Penyederhanaan

Melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tidak perlu atau aturan produksi yang tidak berarti.
Contoh 1 :
S -> AB | a
A -> a
• Aturan produksi S -> AB tidak berarti karena B tidak memiliki penurunan

Contoh 2 :

S->A
A->B
B->C
C->D
D -> a | A
• Memiliki kelemahan terlalu panjang jalannya padahal berujung pada S -> a,
• produksi D -> A juga menyebabkan kerumitan.

Suatu tata bahasa bebas konteks dapat disederhanakan dengan melakukan cara berikut ini:
1. Penghilangan produksi useless ( tidak berguna )
2. Penghilangan produksi unit
3. Penghilangan produksi ε

Penghilangan Produksi Useless

Di sini produksi useless didefinisikan sebagai :
• Produksi yang memuat symbol variabel yang tidak memiliki penurunan yang akan menghasilkan terminal-terminal seluruhnya.
• Produksi yang tidak akan pernah dicapai dengan penurunan apapun dari simbol awal, sehingga produksi itu redundan ( berlebih ).

Contoh 1 :

S -> AB | C

B -> c | Ab

C -> bCb | adF | ab

F -> cFB

Dapat disimpulkan :

1. Aturan Produksi B -> Ab ( A tidak memiliki penurunan)

2. Aturan Produksi F -> cFB (F tidak memiliki penurunan yang menuju simbol terminal)

3. Aturan Produksi C -> adF (F tidak memiliki penuruanan)

Maka produksi yang useless :

B -> Ab

F -> cFB

C -> adF

Maka tata Bahasa bebas konteks setelah disederhanakan menjadi:

S -> aB | C

B -> e

C -> bcb | ab

Contoh 2 :

S-> Aa | B

A->ab | D

B->b | E

C-> bb

E-> aEa

Dapat disimpulkan  :
1) Aturan produksi A -> D, simbol variabel D tidak memiliki penurunan.
2) Aturan produksi C -> bb, Penurunan dari simbol S, dengan jalan manapun tidak akan pernah mencapai C.
3) Aturan produksi E -> aEa, Simbol variabel E tidak memiliki aturan produksi yang menuju terminal.
4) Konsekuensi no (3) Aturan produksi B -> E, simbol variabel E tidak memiliki penurunan.

Maka produksi yang useless :

A -> D
C -> bb

E -> aEa

B -> E

Maka tata Bahasa bebas konteks setelah disederhanakan menjadi:

S -> Aa | B

A -> ab

B -> b

Penghilangan Produksi Unit

• Produksi dimana ruas kiri dan kanan aturan produksi hanya berupa satu simbol variabel,      misalkan: A -> B, C > D.
• Keberadaannya membuat tata bahasa memiliki kerumitan yang tak perlu.

• Penyederhanaan dilakukan dengan melakukan penggantian aturan produksi unit.

Contoh 1 :

S -> Aa | B

B -> A | bb

A -> a | bc | b

Langkah – Langkah penggantian yang dilakukan :

S -> Aa’

S -> B a  | bc  | bb

B -> A a | bc  | bb

B -> bb

A -> a

A -> bc

A -> B bb

Sehingga aturan produksi setelah penyederhanaan :

S -> Aa | a | bc | bb

B -> a | bc | bb

A -> a | bc | bb

Contoh 2 :

S -> A | aa

A -> B

B -> c | b

C -> D | ab

D -> b

Langkah – Langkah penggantian yang dilakukan :

C -> D | ab menjadi C -> b | ab

B -> c | b menjadi B -> b | ab , B -> ab | b

A -> B menjadi A -> ab | b

S -> A menjadi S -> ab | b | Aa

Sehingga aturan produksi setelah penyederhanaan :

S -> ab | b | Aa

A -> ab | b

B -> ab | b

C -> b | ab

D -> b

Penghilangan Produksi ε

·         Produksi ε adalah produksi dalam bentuk

α -> ε atau bisa dianggap sebagai produksi kosong ( empty ).

Penghilangan produksi ε dilakukan dengan melakukan penggantian produksi yang memuat variabel yang bisa menuju produksi ε, atau biasa disebut nullable.

Contoh 1 :

S -> AB

A -> bA | aca | ε

B -> bA | BB | ε

C -> ε

Variabel yang nullable adalah A, B, C. dari S -> AB maka S juga disebut nullable

S -> AB menjadi S -> AB | A | B

A -> abB menjadi A -> abB | ab

A -> aca  menjadi A -> aa

B -> bA menjadi B -> bA | b

B -> BB menjadi B -> BB | B

C -> ε , B -> ε dan A -> ε maka dihafus

Hasil penyederhanaan menjadi :

S -> AB | A | B

A -> abB | ab | aa

B -> bA | b | BB | B

Contoh 2 :

S -> aBcD | bb | ε

A -> cDa | cf

B -> b | af | ε

C -> Bbc | ea

Variabel yang nullable adalah S, B, D.

S -> aBcD menjadi S -> aBc | ac

A -> cDa menjadi A -> Ca

C -> Bbc menjadi C -> Bbc | bc

S -> ε, B -> ε, dan D -> ε maka dihafus

Hasil penyederhanaan menjadi :

S -> aBc | ac | bb | A

A -> Ca | ef

B -> b | Af

C -> BbC | bc | εa

Latihan Kompleks

Lakukan Penyederhanaan pada Himpunan produksi dengan penghilangan Empty + Unit + Useless sekaligus

S -> Baca

B -> Ac

A -> dc | ε

C -> D  | ε

D -> d

Hasil Penyederhanaan Empty (ε)

Langkah 1, hilangkan ε dan C

S -> BACa | Baa

B -> AC | A

A -> dC | ε | d

C -> D

D -> d

Lankah 2, hilangkan ε pada A

S -> BACa  | Baa

B -> AC  | A

A -> dC  | ε | d

C -> D

D -> d

Langkah 3, hilangkan ε pada B

S -> BACa | Baa | Ba | Aca | Aa | Ca | a

B -> AC | A | C

A -> dC | d

C -> D

D -> d

-selesai- pada Langkah Penyederhanaan empty (ε)

Hasil Penyederhanaan Unit

C -> diubah menjadi C - d

B ->  diubah menjadi B – d

B -> diubah mejadi B – dC | d

Jadi

S -> BaCa  | Baa  | BCa  | Ba  | Aca  |  Aa  |  Ca  |  a

B -> AC  |  dC  |  d

A -> dC  |  d

C -> d

D -> d

-selesai  pada Penyederhanaan Unit

Karena syarat Useless tidak ada yang terpenuhi maka langkah penyederhanaan selesai.

Berikut ini video penjelasan dari Latihan soal diatas :