SEKILAS "TBA"
assalamualakummm, haii watzapppp
all , nahhh di postingan ke 10 aku ini akan bahsa tentang pengantar dari teori
bahasa dan otomata nih , sebelumnya kaian udah pada tau nggak apa itu teori
bahasa dan otomata, jika belumm langsung
aja nih kita akan bahas tentang ini.......................lets
go..................
v TEORI BAHASA
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
v 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
langkahlangkah 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.
v Sejarah
Otomata dan Teori Bahasa
Otomata bermula sebelum
komputer ada pada teori di bidang sistem logika matematika atau formal, ilmuwan
David Hilbert telah mencoba menciptakan algoritma umum untuk pembuktian
(seluruh) persoalan matematika secara otomatis yaitu mampu menentukan salah
benarnya sembarang prosisi matematika.
Tahun 1931, Kurt GÖdel
mempublikasikan teori ketidaklengkapan dimana membuktikan prosedur/algoritma
yang dikehendaki David Hilbert tersebut tidak akan pernah ada.
GÖdel membangun rumus di
kalkulus predikat yang diterapkan pada bilangan bulat yang memiliki
pernyataan-pernyataan definisi yang tidak dapat dibuktikan maupun dibantah di
dalam sistem logika yang mungkin dibangun manusia.
Formalisasi argumen teorema
ketidaklengkapan GÖdel ini berikut penjelasan dan formalisasi selanjutnya dari
prosedur efektif secara intuisi merupakan salah satu pencapaian intelektual
terbesar abad 20, yaitu abad dimana formalisasi berkembang semarak.
Pengembangan teori otomata,
komputasi dan teori bahasa berikutnya difasilitasi perkembangan bidang psyco-linguistic.
Bidang psyco-linguistic berupaya menjawab pertanyan-pertanyan berikut:
- Apakah bahasa secara umum?
- Bagaimana manusia
mengembangkan bahasa?
- Bagaimana manusia memahami
bahasa?
- Bagaimana manusia
mengajarkan bahasa ke anak-anaknya?
- Apa gagasan-gagasan yang
dapat dinyatakan dan bagaimana caranya?
- Bagaimana manusia membangun
kalimat-kalimat dari gagasan-gagasan yang berada di pikirannya?
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
Semua aturan produksi
dinyatakan dalam bentuk “” dimana
- : simbol?simbol pada ruas
kiri aturan produksi
- : simbol?simbol pada ruas
kanan
Simbol?simbol tersebut bisa
berupa simbol terminal atau non terminal/ variabel.
Keterangan :
Simbol terminal biasanya
dinyatakan dengan huruf kecil, misal 'a ', ‘b’, ‘c’.(tidak bisa diturunkan
lagi).
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 :
Tidak memiliki produksi
useless
Tidak memiliki produksi unit
Tidak memiliki ?
Langkah?langkah pembentukan
bentuk normal chomsky secara umum:
Biarkan aturan produksi yang
sudah dalam bentuk normal Chomsky.
Lakukan penggantian aturan
produksi yang ruas kanannya mermiat simbol terminal dan panjang ruas kanan >
1
Lakukan penggantian aturan
produksi yang ruas kanannya mernuat >2 simbol variabel
Penggantian?penggantian tersebut bisa dilakukan berkali?kali sampai akhirnya
semua aturan produksi dalam bentuk normal chomsky
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
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.
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
nahhhhh sekarang udah paham kan tentang teori bahasa dan otomata hehehhe
, terimakasih dan semoga blog ini bermanfaat yahh , nahhh untuk lebih jelasnya
tunggu blog aku berikutnya ya aku akan bahas contoh contoh dari nfa dan dfa itu
sendiri dan aku akan jelasin juga tentang pohon kemungkinan nahhhh stay tune
yaaaaaaa ahahahhaahhah , enjoyyy....byee....assalamualaikum wr.wb
Komentar
Posting Komentar