TEORI BAHASA AUTOMATA
Teori bahasa membicarakan bahasa formal (formal language),
terutama untuk kepentingan perancangan kompilator (compiler) dan
pemroses naskah (text processor). Bahasa formal adalah
kumpulan kalimat. Semua kalimat dalam sebuah bahasa dibangkitkan
oleh sebuah tata bahasa (grammar) yang sama. Sebuah bahasa formal bisa
dibangkitkan oleh dua atau lebih tata bahasa berbeda. Dikatakan bahasa formal
karena grammar diciptakan mendahului pembangkitan setiap kalimatnya. Tata
bahasa (grammar) adalah kaidah/aturan pembentukan kata/kalimat. Pada
pembahasannya, bahasa formal hanya disebut bahasa saja.
Bahasa dalam bentuk
tulisan terdiri atas symbol-simbol satuan yang jika dikombinasikan akan
mempunyai arti yang berbeda. Simbol-simbol yang biasa dipergunakan dalam sebuah
bahasa terbatas jumlahnya, yang membentuk sebuah himpunan dan disebut sebagai
abjad/alphabet. Namun kadangkala digunakan istilah karakter yang artinya
sama dengan symbol. Deretan dari karakter atau symbol ini membentuk string. Dan
himpunan dari semua string yang dibentuk dari suatu abjad ini didefinisikan
sebagai bahasa.
Karena bahasa adalah sebuah
himpunan dari string, maka untuk mendefinisikan suatu bahasa bisa dilakukan
dengan menuliskan semua string yang menjadi anggotanya.
Tata Bahasa G = (T,N,S,P), di mana
• T adalah himpunan
berhingga simbol-simbol terminal
• N adalah himpunan
berhingga simbol-simbol non terminal
• S adalah simbol
awal, S ( N )
• P adalah himpunan
berhingga aturan produksi yang setiap elemennya berbentuk * + ,,
*, , ( (T U N)+, *
harus berisi minimal 1 simbol non terminal.
Sentential form adalah semua
string yang dapat diturunkan dari simbol awal S dengan
menggunakan aturan
produksi P.
Kalimat (sentence) adalah sentential
form yang tidak
mengandung simbol non
terminal. Bahasa yang dihasilkan dari G dinotasikan dengan
L(G),
yaitu himpunan kalimat yang dapat diturunkan dari S dengan menggunakan P.
AUTOMATA
Automata berasal dari
bahasa Yunani automatos, yang berarti sesuatu yang bekerja secara otomatis
(mesin). Istilah automata merupakan bentuk tunggal, sedangkan bentuk jamaknya
adalah automaton. Teori automata adalah teori tentang mesin
abstrak yang bekerja secara sekuensial yang menerima dan mengeluarkan output
dalam bentuk diskrit.
Pengertian mesin bukan hanya mesin elektronis/mekanis saja
melainkan segala sesuatu (termasuk perangkat lunak) yang memenuhi ketiga
ciri di atas. Penggunaan automata pada perangkat lunak terutama pada pembuatan
kompiler bahasa pemrograman. Secara garis besar ada dua fungsi automata dalam
hubungannya dengan bahasa, yaitu :
· fungsi automata
sebagai pengenal (RECOGNIZER) string-string dari suatu bahasa, dalam hal ini
bahasa sebagai masukan
dari automata
· fungsi automata sebagai pembangkit (GENERATOR) string-string dari suatu bahasa, dalam hal ini
bahasa sebagai keluaran dari
automata.
Untuk mengenali
string-string dari suatu bahasa, akan dimodelkan sebuah automaton
yang memiliki komponen
sebagai berikut :
- pita masukan, yang menyimpan string masukan yang akan
dikenali;
- kepala pita (tape head), untuk membaca/menulis ke pita
masukan;
- Finite State Controller (FSC), yang berisi status-status dan
aturan-aturan yang
mengatur langkah yang dilakukan oleh automaton berdasarkan
status setiap saat
dan simbol masukan yang sedang dibaca oleh kepala pita;
- pengingat (memory), untuk tempat penyimpanan dan pemrosesan
sementara
Automaton pengenal, setelah membaca string masukan dan melakukan
langkah - langkah pemrosesan yang diperlukan, akan mengeluarkan keputusan apakah
string tersebut dikenali atau tidak.
- Konfigurasi adalah suatu mekanisme untuk menggambarkan keadaan
suatu mesin
pengenal , yang terdiri atas :
_ status FSC
_ isi pita masukan dan posisi kepala pita
_ isi pengingat
Mesin pengenal bersifat deterministik bila
dalam setiap konfigurasi, hanya ada satu kemungkinan yang dapat dilakukan
mesin, jika tidak mesin pengenal bersifat nondeterministik.
Sejarah Automata
Sekitar tahun 1950-an,
Noam Chomsky menciptakan model matematika sebagai sarana untuk mendeskripsikan
bahasa serta menjawab pertanyaan-pertanyaan di atas. Saat ini dimulai
pendalaman bidang bahasa komputer.
Perbedaan antara bahasa komputer dan bahasa manusia adalah sampai sekarang belum diketahuinya bagaimana cara manusia
mengartikan bahasa, sementara dengan
pasti dapat mengartikan bahasa
pada komputer.
Noam Chomsky mengemukakan perangkat format disebut grammar untuk memodelkan
properti-properti bahasa.
Tata bahasa (grammer)
bisa didefinisikan secara, formal sebagai kumpulan dari
himpunan?himpunan variabel, simbol?simbol, terminal, simbol awal, yang dibatasi
oleh aturan?aturan produksi.
Tingkat bahasa dapat
digolongkan menjadi empat yaitu :
1.Bahasa : Regular type 3
Mesin
otomata : Finite State Otomata
(FSA) meliputi deterministic finite automata dan non deterministic finite
automata
Batasan
aturan produksi : adalah sebuah simbol
variabel maksimal memiliki sebuah simbol variabel yang bila terletak di posisi
paling kanan.
2.Bahasa : Bebas konteks/context free
/type 2
Mesin otomata : Push down automata (PDA)
Batasan aturan
produksi : Berupa sebuah simbol variabel.
3.Bahasa : Context sensitive/type 1
Mesin otomata : Linier bounded automata
Batasan aturan
produksi :
4.Bahasa : Unrestricted /phase /natural
language/type 0
Mesin otomata : Mesin turing
Batasan aturan produksi : Tidak ada batasan
a. Semua aturan
produksi dinyatakan dalam bentuk “” dimana
- : simbol?simbol pada
ruas kiri aturan produksi
- : simbol?simbol pada
ruas kanan
b. Simbol?simbol tersebut bisa berupa simbol
terminal atau non terminal/ variabel.
Keterangan :
a. Simbol terminal biasanya dinyatakan dengan
huruf kecil, misal 'a ', ‘b’, ‘c’.(tidak bisa diturunkan lagi).
b. Simbol non terminal dinyatakan dengan huruf
besar, misal ‘A’, ‘B’, ‘C’.(masih bisa diturunkan).
Dengan menerapkan
aturan produksi, suatu tata bahasa bisa menghasilkan string. Himpunan semua
string tersebut adalah bahasa yang didefinisikan oleh tata bahasa tersebut.
Reguler
Pada bahasa reguler, batasannya bertambah dengan ruas kanan
maksimal memiliki sebuah simbol variabel yang terletak di paling kanan. Artinya
bisa memiliki simbol terminal saja dalam jumlah tidak dibatasi, tetapi bla
terdapat simbol variabel tersebut hanya bejumlah satu (1) dan terletak di
posisi paling kanan.
Misal :
Bentuk normal chomsky
/ chomsky normal form (CNF ) merupakan salah satu bentuk normal yang sangat
berguna untuk tata bahasa bebas konteks ( CFG ). Bentuk normal chomsky dapat di
buat dari tata bahasa bebas konteks yang telah mengalami penyederhanaan yaitu
penghilangan produksi useless, unit, dan ? . dengan kata lain, suatu tata
bahasa bebas konteks dapat dibuat menjadi bentuk normal chomsky dengan syarat :
a.Tidak memiliki
produksi useless
b.Tidak memiliki
produksi unit
c.Tidak memiliki ?
Langkah?langkah
pembentukan bentuk normal chomsky secara umum:
a. Biarkan aturan
produksi yang sudah dalam bentuk normal Chomsky.
b. Lakukan penggantian
aturan produksi yang ruas kanannya mermiat simbol terminal dan panjang ruas kanan > 1
c. Lakukan penggantian
aturan produksi yang ruas kanannya mernuat >2 simbol variabel
d. Penggantian?penggantian
tersebut bisa dilakukan berkali?kali sampai akhirnya semua aturan produksi
dalam bentuk normal chomsky
e. Selama dilakukan
penggantian, kemungkinan kita akan memperoleh aturan?aturan produksi baru, dan
juga memunculkan simbol?simbol variabel baru.
Free Context
Bahasa bebas konteks menjadi
dasar dalam pembentukan suatu proses analisis sintaksis. Pada bahasa bebas konteks, batasannya
bertambah lagi dengan ruas kiri haruslah tepat satu symbol variable.
Contoh: B ? CdeFg ; D
? BcDe
a.
Sensiteve Context
Pada bahasa context
sensitive, panjang string pada ruas kiri panjang ruas kanan ( )
Contoh : Abc ? Def ;
CD ? eF
Batasan context sensitive biasanya turut digunakan
dalam proses analitis semantik pada tahapan kompilasi.
b.
Unrestricted /phase /natural language
Bahasa manusia / bahasa alami termasuk ke
dalam grammer (tata bahasa) type 0 /unrestricked, di mana tidak ada batasan
pada aturan produksinya.
Contoh : Abc ? De
BEBERAPA PENGERTIAN DASAR
· Simbol adalah sebuah
entitas abstrak (seperti halnya pengertian titikdalam geometri).
Sebuah huruf atau sebuah angka adalah contoh simbol.
· String adalah deretan
terbatas (finite) simbol-simbol. Sebagai contoh, jika a, b,
dan c adalah tiga buah simbol maka abcb adalah
sebuah string yang dibangun dari ketiga simbol tersebut.
· Jika w adalah
sebuah string maka panjang string dinyatakan sebagai |w| dan
didefinisikan sebagai cacahan (banyaknya) simbol yang menyusun string tersebut.
Sebagai contoh, jika w = abcb maka |w|=
4.
· String hampa adalah
sebuah string dengan nol buah simbol. String hampa dinyatakan dengan simbol ε
(atau ^) sehingga |ε|= 0. String hampa dapat dipandang sebagai simbol hampa
karena keduanya tersusun dari nol buah simbol.
· Alfabet adalah
hinpunan hingga (finite set) simbol-simbol
OPERASI DASAR STRING
Diberikan dua string
: x = abc, dan y = 123
· Prefik string w adalah
string yang dihasilkan dari string w dengan
menghilangkan nol atau lebih simbol-simbol paling belakang
dari string wtersebut.
Contoh : abc, ab, a,
dan ε adalah semua Prefix(x)
· ProperPrefix
string w adalah string yang dihasilkan dari string w dengan
menghilangkan satu atau lebih simbol-simbol paling belakang
dari string wtersebut.
Contoh : ab, a,
dan ε adalah semua ProperPrefix(x)
· Postfix (atau Sufix)
string w adalah string yang dihasilkan dari string wdengan
menghilangkan nol atau lebih simbol-simbol paling depan dari
string w tersebut.
Contoh : abc, bc, c,
dan ε adalah semua Postfix(x)
· ProperPostfix (atau
PoperSufix) string w adalah string yang dihasilkan dari
string w dengan menghilangkan satu atau lebih
simbol-simbol paling depan dari string w tersebut.
Contoh : bc, c,
dan ε adalah semua ProperPostfix(x)
· Head string w adalah
simbol paling depan dari string w.
Contoh : a adalah Head(x)
· Tail string w adalah
string yang dihasilkan dari string w dengan menghilangkan
simbol paling depan dari string w tersebut.
Contoh : bc adalah Tail(x)
· Substring string w adalah
string yang dihasilkan dari string w dengan
menghilangkan nol atau lebih simbol-simbol paling depan
dan/atau simbol-simbol paling belakang dari string w tersebut.
Contoh : abc, ab, bc, a, b, c,
dan ε adalah semua Substring(x)
· ProperSubstring
string w adalah string yang dihasilkan dari string wdengan
menghilangkan satu atau lebih simbol-simbol paling depan
dan/atau simbolsimbol paling belakang dari string w tersebut.
Contoh : ab, bc, a, b, c,
dan ε adalah semua Substring(x)
· Subsequence
string w adalah string yang dihasilkan dari string w dengan
menghilangkan nol atau lebih simbol-simbol dari string w tersebut.
· ProperSubsequence string w Contoh : abc, ab, bc, ac, a, b, c,
dan ε adalah semua Subsequence(x)adalah string yang dihasilkan dari string wdengan
menghilangkan satu atau lebih simbol-simbol dari string wtersebut.
Contoh : ab, bc, ac, a, b, c,
dan ε adalah semua Subsequence(x)
· Concatenation adalah
penyambungan dua buah string. Operator concatenation adalah concate atau
tanpa lambang apapun.
Contoh : concate(xy) = xy = abc123
· Alternation adalah
pilihan satu di antara dua buah string. Operator alternation adalah alternate atau
| |.
Contoh : alternate(xy) = x|y = abc atau 123
· Kleene Closure : x*
= ε|x|xx|xxx|… = ε|x|x 2 |x 3 |…
Positive Closure : x + = x|xx|xxx|…
= x|x 2 |x 3 |…
SIFAT OPERASI DASAR
STRING
· Tidak selalu berlaku
: x = Prefix(x)Postfix(x)
· Selalu berlaku : x = Head(x)Tail(x)
· Tidak selalu berlaku : Prefix(x) =
Postfix(x) atau Prefix(x) ≠ Postfix(x)
· Selalu berlaku : ProperPrefix(x) ≠ ProperPostfix(x)
· Selalu berlaku : Head(x) ≠ Tail(x)
· Setiap Prefix(x), ProperPrefix(x),
Postfix(x), ProperPostfix(x), Head(x), dan
Tail(x) adalah Substring(x),
tetapi tidak sebaliknya
· Setiap Substring(x) adalah Subsequence(x),
tetapi tidak sebaliknya
· Dua sifat aljabar concatenation :
♦ Operasi concatenation bersifat
asosiatif : x(yz) = (xy)z
♦ Elemen identitas operasi concatenation
adalah ε : εx = xε = x
· Tiga sifat aljabar alternation :
♦ Operasi alternation bersifat komutatif
: x|y = y|x
♦ Operasi alternation bersifat asosiatif
: x|(y|z) = (x|y)|z
♦ Elemen identitas operasi alternation
adalah dirinya sendiri : x|x = x
· Sifat distributif concatenation terhadap
alternation : x (y|z) = xy|xz
· Beberapa kesamaan :
♦ Kesamaan ke-1 : (x*)* = (x*)
♦ Kesamaan ke-2 : ε|x + = x +
|ε = x*
♦ Kesamaan ke-3 : (x|y)*
= ε|x|y|xx|yy|xy|yx|… = semua
string yang
merupakan concatenation dari nol atau
lebih x, y, atau keduanya.
Tidak ada komentar:
Posting Komentar