UAS BAHASA DAN AUTOMATA (Regular Grammars dan FSA (NFA))

Regular Grammars

Tata Bahasa (grammer) didefinisikan dengan empat (4) tupel G = ({S, A, B, C, D}) dimana :

   V = Himpunan simbol variabel / non terminal

T = Himpunan simbol terminal

P = Kumpulan aturan produksi

S = Simbol  awal

Kita masih ingat dengan aturan produksi dari bahasa regular (tipe 3) yaitu :

α  à β

α   adalah sebuah simbol variabel.

β     maksimal memiliki sebuah simbol variabel yang bila ada terletak diposisi paling kanan.

Batasannya  bertambah  lagi,  dimana  ruas  kanan  maksimal  memiliki  sebuah  simbol variabel  yang  terletak  paling  kanan.  Artinya  bisa  memiliki  simbol  terminal  dengan jumlah tidak dibatasi, tetapi bila terdapat simbol variabel maka simbol variabel tersebut hanya berjumlah satu (1) dan terletak paling kanan.

Dalam mengkonstruksi aturan produksi tata bahasa regular dari suatu FSA , perlu kita ingat yang menjadi perhatian adalah state-state yang bisa menuju ke state akhir.

Contoh 1 : Mesin FSA

Pada mesin FSA contoh 1, memiliki simbol input ‘a’ dan ‘b’.

•     Misal kita identikan state awal qo dengan simbol awal S.

δ (q0, a) = q1

Dapat ditulis : Sà aA

Dimana A kita identikan dengan q1.

Dapat ditulis :

Aà A               Bà C

dan begitu seterusnya mengikuti state yg sudah di ubah jadi simbol.

Dimana A kita identikan dengan q0 dan B kita identikan dengan q1.

Secara formal dapat ditulis : V = {S, A, B, C, D}

T = {a, b}

P = { Sà aA , SàbB, Aà bC , Bà aB, BàC, CàD,DàaD, Dàb  }

 S = S

Lalu kita masukan inputan (P) ke Jflap Grammer

Selanjutnya “convert to Grrammar”

NFA

Nondeterministic Finite Automata (NFA) adalah salah satu bagian dari otomata berhingga atau Finite State Automata (FSA). ... Nondeterministic Finite Automata(NFA) didefenisikan sebagai M yang merupakan sebuah koleksi dari 5 obyek (Q , Σ , s , F , ∆ )

Suatu string diterima oleh DFA bila terdapat suatu urutan transisi sehubungan dengan input string tsb dari state awal sampai stateakhir.

•NFA harus dicoba semua kemungkinan yang ada sampai terdapat satu yang mencapai state akhir.

Q= {q0, q1, q2, q3, q4}

∑= {a,b}

S= q0

F= {q1}

ᵟ=   

Q	a	b
Q0	Q1	Q2
Q1	Q0	Q1
Q2	Q4	-
Q3	-	Q0
Q4	Q4	Q3

Contoh inputan

·         Inputan (a,a,b,a,b) =hasilnya riject karena tidak menuju ke state akhir

·         Input (a,a,a)  =hasilnya Accept karena menuju ke state akhir

·         Input (a,a,b,b)  =hasilnya Accept karena  menuju ke state akhir

SEKIAN TERIMAKASIH :)