ATURAN PRODUKSI TEORY BAHASA AUTO MATA

 1. TEORI BAHASA DAN OTOMATA ATURAN PRODUKSI UNTUK SUATU FINITE STATE AUTOMATA IFVI.

 Aturan Produksi Bahasa RegulerTata Bahasa (grammer) didefinisikan dengan empat (4) tupel G = ({V, T, P, S}) dimana :V = Himpunan simbol variabel / non terminalT = Himpunan simbol terminalP = Kumpulan aturan produksiS = Simbol awalVI.1 Aturan Produksi Bahasa RegulerKita masih ingat dengan aturan produksi dari bahasa regular (tipe 3) yaitu : α β α adalah sebuah simbol variabel. β maksimal memiliki sebuah simbol variabel yang bila ada terletak dipo  

 1. TEORI BAHASA DAN OTOMATA ATURAN PRODUKSI UNTUK SUATU FINITE STATE AUTOMATA IFVI. Aturan Produksi Bahasa RegulerTata Bahasa (grammer) didefinisikan dengan empat (4) tupel G = ({V, T, P, S}) dimana :V = Himpunan simbol variabel / non terminalT = Himpunan simbol terminalP = Kumpulan aturan produksiS = Simbol awalVI.1 Aturan Produksi Bahasa RegulerKita 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 simbolvariabel yang terletak paling kanan. Artinya bisa memiliki simbol terminal denganjumlah tidak dibatasi, tetapi bila terdapat simbol variabel maka simbol variabel tersebuthanya berjumlah satu (1) dan terletak paling kanan.
  
 2. VI.2 Mengkonstruksi Aturan Produksi dari Suatu Finite State AutomataDalam mengkonstruksi aturan produksi tata bahasa regular dari suatu FSA , perlu kitaingat yang menjadi perhatian adalah state-state yang bisa menuju ke state akhir.Contoh 1 : Mesin FSA a ε q2 b a q0 q1 q4 b ε q3 bPada 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  aE Dimana E kita identikan dengan q1.• Dari q1 terdapat transisi : δ (q1, ε) = q2 dan δ (q1, ε) = q3 Dapat ditulis :
  
 3. EA EB Dimana A kita identikan dengan q2 dan B kita identikan dengan q3.• Selanjutnya dapat kita lihat, dari state q2 dengan input ‘a’ kembali ke state q2 dan dari state q3 dengan input ‘b’ kembali ke state q3. δ (q2, a) = q2 dan δ (q3, b) = q3 Dapat ditulis : A  aA B  bB• Selanjutnya, dari state q2 dengan input ‘b’ menuju state q4 dan dari state q3 dengan input ‘b’ menuju ke state q4. Sementara q4 adalah himpunan state akhir dan dari state q4 tidak ada lagi busur keluar, maka : δ (q2, b) = q4 dan δ (q3, b) = q4 Dapat ditulis : Ab Bb• Kumpulan aturan produksi yang kita peroleh bisa ditulis sebagai berikut : S  aE EA|B A  aA | b B  bB | bSecara formal dapat ditulis :V = {S, E, A, B}T = {a, b}
  
 4. P = { S  aE , E  A | B , A  aA | b , B  bB | b }S=SVI.3 Finite State Automata untuk suatu TataBahasa RegulerJika sebelumnya dari suatu diagram transisi FSA dapat dibuat aturan-aturan produksi tatabahasa regularnya, maka sebaliknya bisa juga mengkonstruksi diagram transisi FSAuntuk suatu tata bahasa regular yang diketahui aturan-aturan produksinya.Contoh 2 : Tata bahasa regularS  aB | bA | εA  abaSB  babSKita dapat langsung gambar atau rancang diagram transisi FSA nya!S identik dengan q0 ; A identik dengan q4; dan B identik dengan q1.Lengkapnya adalah sebagai berikut : b a q1 b a q0 q2 q3 a b q4 q5 q6 a b