PENGANTAR TEORI BAHASA OTOMATA
PENGANTAR TEORI BAHASA OTOMATA
" Assalamualaikum wr.wb selamat pagi,siang,sore atau malam brothers semua,kali ini saya akan membahas tentang Apa aja sih yang ada di dalam Matakuliah Teori Bahasa Otomata? so,Check this out brothers!! "
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.
- Bahasa Natural/manusia bersifat sebaliknya; grammar diciptakan untuk meresmikan kata-kata yang hidup di masyarakat. Dalam pembicaraan selanjutnya ‘bahasa formal’ akan disebut ‘bahasa’ saja.
AUTOMATA
 |
Automata adalah mesin abstrak yang dapat mngenali (recognize), menerima (accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu.Untuk memodelkan hardware dari komputer diperkenalkan otomata. Otomata adalah fungsi-fungsi dari komputer digital. Menerima input, mengh asilkan output, bisa memiliki penyimpanan sementara dan mampu membuat keputusan dalam mentransformasikan input ke output.Sebuah bahasa formal adalah suatu abstraksi terdiri dari himpunan simbol-simbol dan aturan-aturan yang mana simbol-simbol tersebut bisa dikombinaasikan ke dalam entitas yang disebut kalimat.
Meskipun bahasa formal yang dipelajari disini lebih sederhana daripada bahasa lebih sederhana daripada bahasa pemrograman, meraka mempunyai banyak hal yang penting. Kita bisa mempelajari banyak tentang bahasa pemrograman dari bahasa formal.Otomata merupakan suatu sistem yang terdiri atas sejumlah berhingga state, dimana state menyatakan informasi mengenai input yan lalu dandapaty dianggap sebagai memory 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.
PENGERTIAN DASAR
Simbol adalah sebuah entitas abstrak (seperti halnya pengertian titik dalam geometri). Sebuah huruf atau sebuah angka adalah contoh simbol. Pada umumnya kita menggunakan huruf kecil (lower case)atau angka untuk melambngkan simbol, dan huruf kecil diakhir alphabet khususnya w,x,y,z untuk melambangkan untai (String).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. Dinyatakan dengan simbol Ɛ (atau ˄) sehingga | Ɛ|=0. String hampa dipandang sebagai simbol hampa karena keduanya tersusun dari nol buah simbol.
Alphabet adalah himpunan hingga (finite set) simbol-simbol. Pada umumnya kita menggunakan lower case untuk melambangkan simbol, dan huruf kecil diakhir alphabet khususnya w, x, y dan z untuk melambangkan untai (String).
Misalnya kita mempunyai sebuah mesin sederhana yang menerima input kata dalam bahasa indonesia, hal ini dilihat pada gambar dibawah:
- ada : diterima,
- adu : diterima,
- add : ditolak.
OPERASI DASAR STRING
Diberikan dua String : x=abc , dan y=123;- PREFIX STRING w adalah String yang dihasilkan dari String w dengan menghilangkan nol atau lebih simbol-simbol paling belakang dari String w tersebut. Contoh : abc, ab, a dan Ɛ adalah semua PREFIX(x).
- PROPERPREFIK STRING w adalah String yang dihasilkan dari String w dengan menghilangkan satu atau lebih simbol-simbol paling belakang dari String w tersebut. Contoh : ab, a dan Ɛ adalah semua PROPERPREFIX(x).
- POSTFIX (atau SUFIX) STRING w adalah String yang dihasilkan dari String w dengan menghilangkan nol atau lebih simbol-simbol paling depan dari String w tersebut. Contoh : abc, bc, c dan Ɛ adalah semua POSTFIX(x).
- PROPERPOSTFIX (atau SUFIX) 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).
- SUBSTRING STRING w adalah String yang dihasilkan dari String w dengan menghilangkan nol atau lebih 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).
- PROPER SUBSTRING STRING w adalah String yang dihasilkan dari String w dengan menghilangkan satu atau lebih simbol paling depan dan/atau simbol-simbol paling belakang dari String w tersebut. Contoh : ab, bc, a, b, c dan Ɛ adalah semua PROPERSUBSTRING (x).
- SUBSEQUENCE STRING w adalah String yang dihasilkan dari String w dengan menghilangkan nol atau lebih simbol-simbol dari String w tersebut. Contoh : abc, ab, bc, ac, a, b, c dan Ɛ adalah semua SUBSEQUENCE (x).
- PROPER SUBSEQUENCE STRING w adalah String yang dihasilkan dari String w dengan menghilangkan satu atau lebih simbol-simbol dari String w tersebut. Contoh : ab, bc, ac, a, b, c dan Ɛ adalah semua SUBSEQUENCE (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 menhilangkan HEAD tersebut. Contoh : bc adalah TAIL(x).
- CONCATENATION adalah penyambungan dua buah String. Contoh : concate(xy) = xy = abc123.
- ALTERNATION adalah pilihan satu diantara dua buah String. Operatornya adalah |. Contoh : alternate(xy) = x | y = abc atau 123.
x* : menyatakan himpunan seluruh untai yang meliputi seluruh alphabet, termasuk untai kosong (Ɛ).
POSITIVE CLOSURE : x+ = x | xx | xxx |… = x | x2 | x3 | …
x+ : menyatakan himpunan seluruh untai meliputi seluruh alphabet, tidak termasuk untai kosong (Ɛ).
Komentar
Posting Komentar