Archive for November 2012

- , |

Teori Bahasa Dan Automata


BAB I. PENDAHULUAN
A.   KEDUDUKAN TEORI BAHASA DAN OTOMATA
      PADA ILMU KOMPUTER
Ilmu komputer mempunyai 2 komponen utama :
•   Model dan gagasan mendasar mengenai komputasi.
•   Teknik rekayasa untuk perancangan sistem komputasi, meliputi perangkat keras dan perangkat lunak, khususnya penerapan rancangan dari teori.
      Teori bahasa dan otomata merupakan bagian pertama.
Secara teoritis ilmu komputer diawali dari sejumlah perbedaan disiplin ilmu.
•   Teknik elektro :Mengembangkan switching  sebagai tool untuk mendesain
hardware.
•   Matematika : Bekerja berdasarkan logika.
•   Ahli Bahasa: Menyelidiki tata bahasa untuk natural language.
•   Ahli Biologi : Mempelajari neural network.
Spesifikasi dari sebuah bahasa pemrograman :
•   Himpunan simbol-simbol (alphabet) yang bisa dipakai untuk membentuk program yang benar.
•   Himpunan program yang benar secara sintaktik.
•   Makna dari program tersebut.
B. Konsep Bahasa dan Otomata
1.Teori Bahasa adalah konsep-konsep pada "string alpabet “ dalam penyambungan karakter-karakter alpabet untuk membentuk suatu makna (bahasa).
2.  Alpabet  adalah himpunan simbol (karakter) tak kosong yang  berhingga. Alpabet digunakan                  untuk membentuk kata-kata (string-string) di bahasa. Bahasa dimulai dengan alpabet. Alpabet dilambangkan dengan Σ
3.String adalah deretan simbol dari alpabet dimana perulangan simbol diijinkan.
Contoh :
V = {a,b,c,d}
String pada alpabet V antara lain -> 'a','abcd','bbba'
4.panjang string adalah jumlah simbol di dalam string bukan pada alpabet dan pengulangan kemunculan simbol dihitung. Panjang string dilambangkan |w|

                        Contoh:
                        |ε| = 0
                        |a| = 1
                        |aa| = 2
                        |aaa| = 3
                        |aaab| = 4
5.Empty  string(null string) adalah string yang tidak mengandung simbol apapun. Lambangnya e                atau l
6.Regular expression adalah cara untuk mengekspresikan bahasa dengan hanya menggunakan operasi :
•   Concatenation
•   Superscript
•   Kleene closure
Positif closure
Penyambungan (Concatenation - o)

Penyambungan dilakukan pada 2 karakter atau lebih membentuk 1 barisan karakter (string simbol).

Contoh :
'a' o 'b' = 'ab'
'ab' o 'baab' = 'abbaab'
Superscript

Penyambungan dapat dianggap sebagai perkalian karena biasanya penulisannya adalah bila x dan y string, maka x o y adalah xy. sehingga pemangkatan dapat digunakan

VoV = VV = V2 ----> Panjang string = 2
Kleene closure
V* = {ε} U V+
adalah string pada V, termasuk string kosong dimana ε string kosong (string tanpa simbol)
ε mempunyai sifat identitas, yaitu:
ε o x = x
x o ε = x
Positive closure
V+ = V1 U V2 U V3 U ...
adalah himpunan string pada V, tidak ada string kosong didalamnya.

V0 = {ε}
adalah himpunan yang isinya hanya string kosong, dimana String kosong ε tidak sama dengan himpunan kosong
• Otomata merupakan suatu sistem yang terdiri atas sejumlah berhingga state, dimana state menyatakan informasi mengenai input yang lalu, dan dapat pula dianggap sebagai memori mesin.
• Input pada mesin otomata dianggap sebagai bahasa yang harus dikenali oleh mesin.
• Selanjutnya mesin otomata membuat keputusan yang mengindikasikan apakah input itu diterima atau tidak.
• Sebuah string input diterima bila mencapai state akhir / final state yang digambarkan dengan lingkaran ganda.
c.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.
• Aturan produksi merupakan pusat dari tata bahasa, yang menspesifikasikan bagaimana suatu tata bahasa melakukan transformasi suatu string ke bentuk lainnya.
• Semua aturan produksi dinyatakan dalam bentuk : “ α→β “ ( alpha menghasilkan betha atau alpha menurunkan betha)
• α menyatakan simbol-simbol pada ruas kiri aturan produksi.
• β menyatakan simbol-simbol pada ruas kanan aturan produksi
• Penggolongan empat tingkatan bahasa berdasarkan hirarki Comsky dapat dilihat pada tabel berikut :



• Simbol variabel / non terminal adalah simbol yang masih bisa diturunkan lagi dan dinyatakan dengan huruf besar.
• Simbol terminal sudah tidak bisa diturunkan lagi, dan dinyatakan dengan huruf kecil.
• Dengan menerapkan aturan produksi, suatu tata bahasa bisa menghasilkan sejumlah string.
• Himpunan semua string adalah bahasa yang didefinisikan oleh tata bahasa tersebut.
Contoh Aturan Produksi
Ø T → a  
      dibaca “T menghasilkan a“
Ø E → T | T + E 
      dibaca   “E menghasilkan T” atau
                                             “E menghasilkan T dan E“
                        Simbol | menyatakan ‘atau’, digunakan untuk mempersingkat penulisan aturan produksi yang mempunyai ruas kiri yang sama.
Tipe 0 /Unrestricted /Natural Language
• Tidak ada batasan pada aturan produksinya.
                     Misal :            Abc → De
                                             ABC → b
Tipe 1/ Conteks Sensitive
• Panjang string pada ruas kiri ≤ panjang string pada ruas kanan |α | ≤ |β|.
                     Misal :
                     Ab → DeF
                     CD → eF
                     exception : S → ε
Tipe 2 / Bebas Konteks/ Context Free
• Ruas kiri harus tepat satu simbol variabel
                     Misal :
                     B → CDeFG
                     D → BcDe
Tipe 3/Reguler
• Ruas kanan maksimal memiliki sebuah simbol variabel yang terletak di paling kanan, simbol terminal bisa berapa saja/ tak terbatas, tetapi bila terdapat simbol variabel harus terletak paling kanan.
                     Misal :            A  → e
                                             A  → fgh
                                                                     A  → eH
                                                                     C  → D
Catatan :
•       Aturan produksi seperti :
                        ε → Abd
                        bukan aturan produksi yang legal, karena simbol ε tidak boleh berada pada ruas kiri  
•       Aturan produksi yang ruas kirinya hanya memuat simbol terminal saja, seperti :
a → bd
ab → bd
bukan aturan produksi yang legal, karena ruas kiri juga harus memuat simbol yang bisa diturunkan.
Bab III FINITE STATE AUTOMATA
A.   Penerapan Finite State Automata.
B.   Finite State Automata/Otomata berhingga state (FSA), bukan suatu mesin fisik, tetapi suatu model matematika dari suatu sistem yang menerima input dan output diskrit.
C.   FSA merupakan mesin otomata dari bahasa reguler.
D.  FSA memiliki state yang banyaknya berhingga, dan dapat berpindah-pindah dari suatu state ke state lain.
Perubahan state dinyatakan oleh fungsi transisi.
Jenis otomata FSA tidak memiki tempat penyimpanan, sehingga kemampuan ‘mengingatnya’ terbatas.
Teori mengenai Finite State Automata adalah suatu tool yang berguna untuk merancang suatu sistem
Arti dari bentuk-bentuk
pada FSA
ž Lingkaran menyatakan state/kedudukan.
ž Label pada lingkaran adalah nama state
ž Busur menyatakan transisi yaitu perpindahan kedudukan/state.
ž  Label pada busur adalah simbol input.
ž  Lingkaran didahului sebuah busur tanpa label menyatakan state awal.
ž  Lingkaran ganda menyatakan state akhir/ final.

Secara formal FSA dinyatakan oleh 5 tupel.
M = (Q, å, δ, S, F )  , dimana :
Q = himpunan state / kedudukan
å = himpunan simbol input / masukkan / abjad.
δ = fungsi transisi.
S = state awal / kedudukan awal (initial state).
F = himpunan state akhir.
Jumlah state akhir pada suatu FSA bisa lebih dari satu.
B. Deterministic Finite Automata(DFA)
    (Otomata Berhingga Deterministik)    
Pada DFA, dari suatu state ada tepat satu state berikutnya untuk setiap simbol masukkan yang diterima.
Q = {q0, q1, q2 }
                        å = {a, b}
                        S = q0
                        F = q2
Fungsi transisi yang ada :
δ(q0,a) = q0
δ(q0,b) = q1
δ(q1,a) = q1
δ(q1,b) = q2
δ(q2,a) = q1
δ(q2,b) = q2
Non Deterministic Finite Automata
( NFA )
ž Pada NFA dari suatu state bisa terdapat 0,1 atau lebih busur keluar/ transisi berlabel simbol input yang sama.
Perbedaan DFA dan NFA ada pada fungsi transisinya, dimana untuk setiap pasangan state input, bisa memiliki 0 atau lebih pilihan untuk state berikutnya

ž Suatu string diterima oleh NFA bila terdapat suatu urutan transisi sehubungan dengan input string tersebut dari state awal menuju state akhir.
ž Untuk NFA, semua kemungkinan yang ada harus dicoba, sampai terdapat satu yang mencapai state akhir.
ž Jadi untuk membuktikan suatu string diterima oleh NFA, harus dibuktikan suatu urutan transisi yang menuju state akhir.
Reduksi Jumlah State pada FSA
ž Untuk bahasa reguler, kemungkinan ada sejumlah DFA yang dapat menerima NFA, perbedaannya ada pada jumlah state yang dimiliki otomata-otomata tersebut.
ž Pilih Otomata dengan jumlah state paling sedikit, dengan tidak mengurangi kemampuannya ‘semula’ untuk menerima suatu bahasa.
ž Distinguishable ( dapat dibedakan)

State p dan q dikatakan distinguishable jika ada string
                        w Î å * sehingga sedemikian :
                        δ (p,w) Î F dan δ (q,w) Ï F
Indistinguishable (tidak dapat dibedakan)

State p dan q dikatakan indistinguishable jika ada string w Î å * sehingga sedemikian :
                        δ (p,w) Î F dan (q,w) Î F
                        atau
                        δ (p,w) Ï F dan δ (q,w) Ï F

ž Pasangan dua buah state memiliki salah satu kemungkinan dari distinguishable atau indistinguishable, tetapi tidak kedua-duanya.
ž Jika p dan q indistinguishable, dan jika q dan r juga indistinguishable, maka p dan r juga indistinguishable, dan ketiga state tersebut indistinguishable
Cara untuk mereduksi state dari suatu DFA
ž Hapus semua state yang tidak dapat dicapai dari state awal.
ž Buat tabel yang menentukan pasangan distinguishable atau in distinguishable.
ž Tentukan pasangan state (p,q) yang distinguishable.
ž Untuk semua pasangan  (p,q) yang mungkin dan w Î S tentukan δ (p,w) = pa dan δ (q,w)  = qb
                                                Jika pasangan (pa,qb) sudah tercakup di langkah 3 (distinguishable) maka pasangan (p,q) juga dikatakan distinguishable.

ž Sisa pasangan-pasangan state lainnya adalah pasangan-pasangan yang indistinguishable dan digabung menjadi satu.
EKIVALENSI DFA KE NFA
Dari sebuah mesin NFA dapat diubah ke DFA yang ekivalen.
Ekivalen artinya mampu menerima bahasa yang sama.

Reduksi Jumlah State pada FSA
¨ Untuk bahasa reguler, kemungkinan ada sejumlah DFA yang dapat menerima NFA, perbedaannya ada pada jumlah state yang dimiliki otomata-otomata tersebut.
¨ Pilih Otomata dengan jumlah state paling sedikit, dengan tidak mengurangi kemampuannya ‘semula’ untuk menerima suatu bahasa.
Distinguishable ( dapat dibedakan)

State p dan q dikatakan distinguishable jika ada string
            w Î å * sehingga sedemikian :
            δ (p,w) Î F dan δ (q,w) Ï F

Indistinguishable (tidak dapat dibedakan)

State p dan q dikatakan indistinguishable jika ada string w Î å * sehingga sedemikian :
            δ (p,w) Î F dan (q,w) Î F
            atau
            δ (p,w) Ï F dan δ (q,w) Ï F

ž Pasangan dua buah state memiliki salah satu kemungkinan dari distinguishable atau indistinguishable, tetapi tidak kedua-duanya.
ž Jika p dan q indistinguishable, dan jika q dan r juga indistinguishable, maka p dan r juga indistinguishable, dan ketiga state tersebut indistinguishable
Contoh :
Mesin DFA dan NFA yang ekivalen.

Algoritma :
¨ Buat semua state yang merupakan subset dari state semula (Q).
      jumlah state menjadi 2Q
¨ Telusuri transisi state–state yang baru terbentuk, dari diagram transisi.
¨ Tentukan state awal : {q0}
¨ Tentukan state akhir adalah state yang elemennya mengandung state akhir.
¨ Reduksi state yang tak tercapai oleh state awal. 
¨ Contoh  Ubahlah NFA berikut menjadi DFA
¨ M={{q0,q1}, {0,1}, d, q0,{q1}} dengan tabel transisi
1. State yang akan dibentuk : {}, {q0} {q1},{q0,q1}
2. Telusuri state
3. State awal : {q0}
4. State akhir yang mengandung q1, yaitu {q1},{q0,q1}
Contoh :  Ubahlah NFA berikut menjadi DFA
¨  M={{q0,q1 ,q2}, {p,r}, d, q0,{q1}} dengan tabel transisi
1.State yang akan dibentuk : {}, {q0} {q1},{q2}, {q0,q1},
                         {q0,q2}, {q1,q2}, {q0,q1,q2}
2.Telusuri state:
¨  3. State awal : {q0}
¨  4. State akhir yang mengandung q1, yaitu {q1},{q1,q2}
¨  5. Reduksi {q0,q1}{q0,q2}{q0,q1,q2 } sehingga FSA menjadi

Contoh :  Ubahlah NFA berikut menjadi DFA
¨  M={{q0,q1 ,q2}, {p,r}, d, q0,{q1}} dengan tabel transisi
1.State yang akan dibentuk : {}, {q0} {q1},{q2}, {q0,q1},
                         {q0,q2}, {q1,q2}, {q0,q1,q2}
2.Telusuri state:
¨  3. State awal : {q0}
¨  4. State akhir yang mengandung q1, yaitu {q1},{q1,q2}
¨  5. Reduksi {q0,q1}{q0,q2}{q0,q1,q2 } sehingga FSA menjadi