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
