TEORI BAHASA DAN AUTOMATA
 |
| Sumber : http://meilany.upy.ac.id |
Bahasa sehari-hari di bentuk dengan
menerapkan serengkaian aturan tata
bahasa(Grammar), namun dalam hal konteks Automata menerapkan
serangkain aturan produksi pada sebuah simbol-simbol. Sedangkan Otomata
dalam dunia matematika adalah mesin sekuensial yang menerima input, dan
mengeluarkan output, dalam bentuk diskrit.
Teori Bahasa Otomata :
-
Pembangkitan kalimat/
generation :menghasilkan semua kalimat dalam bahasa L berdasarkan berdasarkan
aturan yang di milikinya.
-
Pengenalan kalimat /
recognition : menentukan suatu string (kalimat) termasuk sebagai salah satu
anggota himpunan L.
Menurut
Noam Chomsky kelas tata bahasa di klarifikasikan dalam beberapa kelas :
1.
Kelas tata bahasa regular
(regular grammar)
Biasanya
di namakan bahasa regular laanguage,
mesin yang mengenalinya adalah Finite
State Automaton (FSA).
2.
Bahasa bebas konteks (context-free grammar)
Sering
di dingkat CFL, mesin yang mengenalinya dinamakan Push Down Automata (PDA).
3.
Kelas tata bahasa
peka-konteks (context-sensitive)
CSL
atau tata bahasa tipe 1, mesin yang mengenali bahasanya di namakan Linier Bounded Automata (LBA).
4.
Tata bahasa tanpa
pembatasan (unnrestricted grammar)
Mesin
yang mengenali bahasa ini adalah Mesin Turing (Turing Machine).
Dalam bentuk tabel.
Kelas Tata Bahasa
|
Mesin Pengenal Bahasa
|
regular
grammar
|
Finite
State Automaton (FSA)
|
context-free
grammar
|
Push
Down Automata (PDA)
|
context-sensitive
|
Linier
Bounded Automata (LBA)
|
unnrestricted
grammar
|
Mesin Turing (Turing
Machine)
|
Operasi Dasar
String Dan Sifat Operasinya
String
merupakan deretan simbol sebagai suatu entitas, di dalamya ada yang bisa muncul
dua kali namun juga ada yang tidak di gunakan. Penulisan string menggunakan
aturan grammatr yang sama(pembentukan) tertentu.
-
Notasi variabel
simbol/string
o Variabel
string tertentu sering di presentasikan dalan bentuk huruf kecil dalam bahas
latin x,y,z dll.
o Variabel
string simbol sering di presentasikan a,b,c.... huruf-huruf kecil pada urutan
awal abjad.
-
Notasi variabel himpunan
dalam string
Variabel untuk humpinan string di
awali dengan huruf kapital pada urutan abjad.
Contoh : L {001,00011,110000}
-
Panjang string tersusun
atas sejumlah n simbol, n ≥ 0, panjang string di tulsi |x|
Contoh |aabba|=5
-
String kosong
Jika |x|=0 maka string x tersebut di
sebut di sebut string kosong.
Contoh model
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 w
tersebut.
Contoh
: abc, ab, a, dan e 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 w
tersebut.
Contoh
: ab, a, dan e 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 e 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 e 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 e adalah semua Substring(x)
·
ProperSubstring string w adalah string yang dihasilkan dari string w dengan
menghilangkan satu atau lebih simbol-simbol paling depan dan/atau simbol-simbol
paling belakang dari string w tersebut.
Contoh
: ab, bc, a, b, c, dan e 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.
Contoh
: abc, ab, bc, ac, a, b, c, dan e adalah semua Subsequence(x)
·
ProperSubsequence 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 e 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* = e½x½xx½xxx½… = e½x½x½x½…
·
Positive Closure : x = x½xx½xxx½… = x½x½x½…
Hubungan
kompleksitas Sebuah Variabel yaitu :
-
Salah satunya
kecerdasan buatan
Bidang ilmu yang mendasarkan bagaimana computer bias
bekerja seperti manusia. Penggunaa kecerdasan buatan meliputi pengolahan
citra, teori kendali, pengenalan
robotika.
-
Lingkup aplikasi
kecerdasan buatan :
1. System pakar
2. Pengolahan Bahasa alami
3. Penganalan Ucapan
4. Robotika
5. System sensor
6. Computer vision
7. Problem solving
8. Permainan
Komentar
Posting Komentar