Teori Bahasa dan Otomata
Teori bahasa
dan otomata merupakan bagian dari teori komputasi pada ilmu komputer.
Beberapa teori komputasi datang dari bahasa dan rekayasa sistem, terutama
yang berbasiskan matematika. Dalam hal ini penekanannya adalah pada
pemecahan masalah. Melalui contoh-contoh ilustrasi-masalah dapat dikenali
latar belakang dari suatu konsep dan hubungannya dengan definis dan
teorema yang ada. Secara teoritis ilmu komputer diawali dari sejumlah
berbeda disiplin ilmu; ahli biologi mempelajari neural network, insinyur
elektro mengembangkan switching sebagai tools untuk mendesain perangkat
keras, matematikawan bekerja berdasarkan logika, dan ahli bahasa menyelidiki
tata bahasa untuk bahasa alami (natural language) Finite state automata
dan ekspresi reguler awal dikembangkan berdasarkan pemikiran neural
network dan switching circuit. Finite state automata merupakan tools
yang sangat berguna dalam perancangan suatu penganalisa leksikal (lexical
analyzer) yang berguna dalam mengelompokkan karakter-karakter kedalam
token-token sebagai unit terkecil dalam mengenali pola. Jadi apa
sesungguhnya teori bahasa tersebut ? Teori bahasa merupakan suatu gagasan
mendasar dalam komputasi yang menjadi tools untuk mengenali persoalan.
Gagasan dasar tersebut dimodel dengan suatu simbol-simbol yang
merepresentasikan juga suatu fungsi dari komputer digital. Teori
bahasa pada awalnya lebih diarahkan untuk mengenali suatu tata bahasa dan dapat
mendefinisikan spesifikasi formal dari tata bahasa tersebut. Sehingga
pada akhirnya dapat didefinisikan langkah-langkah algoritmik dalam
pemrosesan tata bahasa.
Teori bahasa dan otomata dalam ilmu komputer
Suatu teori
hanya menarik jika dapat membantu dalam mencari solusi terbaik.
Tanpa penerapan timbul pertanyaan, mengapa mempelajari teori? Teori
memberikan konsep dan prinsip yang menolong untuk memahami perilaku
dari suatu persoalan yang berkorelasi dengan teori tersebut. Bidang ilmu
komputer meliputi topik yang luas, dari perancangan mesin sampai
pemrograman. Disamping perbedaan yang ada, terdapat keseragaman
prinsip-prinsip umum yang dipakai. Untuk mempelajari prinsip-prinsip dasar
tersebut, kita mengkonstruksi suatu mesin otomata sebagai model abstrak
dari komputer dan komputasi. Model ini memiliki fungsi-fungsi yang penting
dan umum pada perangkat keras dan perangkat lunak komputer. Meskipun model
tersebut sederhana untuk diterapkan langsung pada dunia nyata, keuntungan
yang diperoleh dari mempelajarinya adalah memberikan landasan untuk basis
dari suatu pengembangan algoritma. Pendekatan ini, juga diterapkan pada
ilmu sains lainnya.
Abjad, Kata, dan Bahasa
- Abjad adalah himpunan berhingga tak
kosong dari simbol.
notasi dari
abjad adalah ∑ "sigma"
contoh
∑ :
{a,b,c,d,...z}
∑ :
{1,2,3,4....}
(a,b,c,d....z
& 1,2,3,4....) adalah sebuah simbol. dan jika di kumpulkan dalam satu
kurung kurawal maka akan menjadi suatu abjad
- Kata/string/untai adalah Barisan berhingga
simbol-simbol dari suatu abjad.
notasi dari
kata/string/untai adalah w "w kecil"
contoh
∑ :
{a,b,c,d.....z}
w1 = saya
w2 = buku dst
∑ :
{1,2,3,4......}
w1 = 1
w2 = 12
w3 = 11 dst
kata
kosong/string kosong : Barisan
yang kosong dari simbol-simbol
notasi dari
string kosong adalah Ɛ
- Bahasa adalah suatu himpunan dari
string-string.
notasi dari
bahasa adalah L
contoh
L1 = bahasa
inggris
L2 = bahasa
jawa
L3 = bahasa
spanyol dll
Nb: setiap
bahasa mempunyai aturan masing-masing, jadi begitu juga dalam otomata dan teori
bahasa dalam membuat bahasa harus ada aturannya
contoh
∑ : {1}
w1 = 1; w2 =11; w3 = 111; w4 = 1111 dst
L1={1,111,1111}"aturannya
: Genap"
L2={11.1111.111111}
"aturannya : Ganjil"
Bahasa
Universal adalah suatu
bahasa yang bisa mengakomodasi semua string dari suatu abjad
notasi
: ∑*
contoh
∑ :
{a,b,c}
∑* :
{Ɛ,a,b,c,d,ab,aa,cc,....}
∑ :
{2}
∑* :
{Ɛ,22,2,222,2222......}
contoh
sederhana
∑ :
{1,2,3}
L :
{1,2,3} -> apa aturannya..??
bahasa itu
menggunakan aturan "satu state tunggal"
->
Panjang (length) dari string
notasi |w|
contoh
w1 = 1 2 1 -> |w1|= 3
w2 = aa -> |w2|=2
->
Perangkaian (concatenation)
contoh
w1 = ab
w2 = 31
w1.w2 = ab.31 -> ab31
->Exponensial
(pangkat)
misal w adalah
kata
w^n = {Ɛ, jika n = 0}
{w.w^n-1 jika n > 0}
dibaca "w pangkat n, w dikalikan dengan
w pangkat n-1"
contoh:
w : ab
w^0 = Ɛ
w^1 = w.w^1-1 = w.w^0 = ab.Ɛ =ab
w^2 = w.w^2-1 = w.w^1 = ab.ab = abab dst
- Operasi-operasi pada Bahasa
->
Perangkaian (concatenation)
misal A dan B
adalah Bahasa
A.B={w1.w2|w1 € A & w2 € B}
contoh:
A = {Rumah}
B = {lia,kucing}
A.B = {Rumah lia, Rumah kucing}
-> Exponensial (Pangkat)
misal A adalah Bahasa
A^n = {{Ɛ}, jika n=0}
{A.A^n-1 jika
n > 1}
contoh
A = {A,B}
A^0 = {Ɛ}
A' = A.A^0 = {AB}.{Ɛ} = {AB}
-> Gabungan (Union)
misal A dan B adalah bahasa
A U B = {w | w € A atau w € B}
contoh
A : {a,ab,c,d}
B : {c,a,aa,dd}
A U B : {a,ab,c,d,aa,dd}
-> Irisan (Lutesectim)
misal A dan B adalah Bahasa
A n B : { w | w € A dan w € B }
dari contoh Gabungan di atas maka irisannya adalah
{C,A} karna {C,A} ada di A dan juga ada di B
-> Sub bahasa
misal A dan B adalah Bahasa
A C B "dibaca A sub bahasa dari B"
jika semua kata anggota A jika merupakan anggota B
contoh
∑ : {a,b}
a C b = ..?
a : {aa,ab,aab,....}
b : {a,b,aa,bb,ab,aab...}
-> Sama (Equal)
misal A dan B adalah Bahasa
A = B jika Semua anggota A merupakan anggota B
dan sebaliknya
A : {a,b}
B : {b,a}
A = B
-> Star Clousure & Plus Clousure
misal A dan B adalah Bahasa
A* ("di baca A star clousure")
Contoh
∑ : {a} "abjad"
A : {aa} "bahasa"
Klasifikasi Tata Bahasa
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:
FINITE STATE AUTOMATA (FSA)
DAN IMPLEMENTASINYA
Finite State
Automata (FSA) adalah suatu mesin abstrak yang digunakan untuk
merepresentasikan penyelesaian suatu persoalan dari suatu sistem
diskrit. Sebagai sebuah mesin maka FSA akan bekerja jika diberikan suatu
masukan. Hasil proses adalah suatu nilai kebenaran diterima atau tidaknya
masukan yang diberikan. FSA memiliki state yang banyaknya berhingga, jika
diberikan suatu simbol input maka dapat terjadi suatu perpindahan dari
sebuah state ke state lainnya. Perubahan state tersebut dinyatakan oleh
suatu simbol transisi. Mekanisme FSA tidak memiliki memori sehingga selalu
mendasarkan prosesnya pada posisi state “saat ini”. Misalnya
pada mekanisme kontrol pada sebuah lift, selalu didasari pada posisi lift
saat itu pada suatu lantai, pergerakan ke atas atau ke bawah dan
sekumpulan permintaan yang belum terpenuhi.
dalam FSA di
bagi menjadi 2 jenis yaitu
- DFA (Deterministic FSA) ->
memiliki hasil yang pasti
- NFA (Non Deterministic FSA)
-> memiliki hasil yang tidak pasti
Secara
formal FSA didefinisikan dengan 5 tuple : M = (Q, Σ, δ, S, F), dimana :
Q : himpunan
state/kedudukan
Σ : himpunan
simbol input
∂ : fungsi
transisi
S : State
awal (initial state)
F : himpunan
state akhir (Final State)
Apa yang
dimaksud DFA?
A deterministic
finite automaton (DFA) M = (Q, Σ, δ, S, F), 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)
Apa yang di
maksud NFA?
A Non deterministic
finite automaton (DFA) M = (Q, Σ, δ, S,Q0, F), dimana :
Q : himpunan
state/kedudukan
Σ :
himpunan simbol input
Q0 € Q : initial state
∂ :
fungsi transisi, dimana ∂ = Q
x (Σ u Ɛ) -> P (Q)
S :
State awal (initial state)
F : himpunan
state akhir (Final State)
contoh DFA
disebut DFA
karena setiap inputan state menerima tepat 1 state berikutnya
Q =
{q0,q1,q2}
∑ = {0,1}
S = {q0}
F = {q1,q2}
∂ = fungsi
transisi
∂ (q0,0) =
q1
∂ (q0,1) =
q2
∂ (q1,0) =
q1
∂ (q1,1) =
q1
∂ (q2,0) =
q2
∂ (q2,1) =
q2
Membuat
table transisi
∂
0 1
q0
q1 q2
q1
q1 q1
q2
q2 q2
contoh NFA
Q = {q0,q1}
∑ = {0,1}
S = {q0}
F = {q1}
∂ = fungsi
transisi
∂ (q0,0) =
q1
∂ (q0,1)
= Ɛ
∂ (q1,0) =
q1
∂ (q1,1) =
q1
Membuat
table transisi
∂
0 1
q0
q1 Ɛ
q1
q1 q1
disebut NFA
karna ada state yang kosong "Ɛ"
dari
contoh-contoh diatas dapat di tulis bahwa perbedaan dari NFA dan DFA sebagai
berikut:
Perbedaan
NFA & DFA
|
DFA
|
Untuk
sebuah state yang berlaku bias di tentukan tepat satu state berikutnya
|
|
δ = (s,w)
= Q € F
è Dibaca “transisi dari state awal dengan inputan
string w dengan hasil state Q anggota F”
S = state
awal
W = string
F = final
state
|
NFA
|
Dari
setiap state dengan inputan yang ada, tidak selalu tepat pada state
berukutnya
|
|
Dari suatu
state bias terdapat 0,1 atau lebih busur (transisi) berlabel input yang sama
|
δ = (s,w)
= {s} dimana δ (s,w) memuat suatu state di dalam F
|
