Pengenalan tentang Bahasa dan Otomata
Bahasa adalah rangkaian simbol-simbol
yang memiliki makna.
Otomata adalah aistem yang terdiri dari
atas sejumlah state, dimana state menyatakan informasi yang diinput.
Hubungan Bahasa dan Otomata
Bahasa ---> Mesin Otomata ---> ada
dua kemungkinan yaitu : 1.diterima (syarat mencapao final state)
2.
Ditolak
Konsep TBO
1. Teori Bahasa = string alfabet
2. Alfabet = Himpunan simbol (karakter)
yang tidak kosong
3. String = Deretan simbol alfabet, cth:
V = {a,b,c,d}
4. Panjang string = jumlah aimbol dalam
string
Cth: |€| = 0 ; |a| = 1 ; |aa|= 2 ; |aaa|= 3 dst.
5. Empty string = string tidak
mengandung simbol.
Cth: lambangnya € atau lamda
6. Regular Expression : cara untuj
mengekspresikan bahasa
- Concatenation (penyambungan)
Cth: 'a' o 'b' = 'ab'
'ab' o 'aabc' = 'abaabc'
- Super script (perkalian)
Cth: 'v' o 'v' = 'vv'
- Kleene Closure (string tanpa simbol)
Cth: 'v' o € = v
- Positif Closure (tidak ada string kosong didalamnya)
*merupakan himpunan string pada V dan tidak ada string kosong didalamnya
Hirarti Chomsky
Bahasa : Regular, level/tipe 3
Mesin Otomata: finite state autonata :
DFA dan NFA .
Aturan :
* simbol sebelah kiri harus berupa simbol variable.
* simbol sebelah kanan maximal hanya memiliki sebuah simbol variable dan
bila ada terletak dipaling kanan.
Bahasa: bebas konteks, level/tipe 2
Mesin Otomata : push down otomata .
Aturan : *simbol sebelah kiri harus
simbol variable.
Bahasa : context sensitive level/tipe 1
Mesin Otomata : Linier Bounded Automata.
Aturan :
*simbol pada sebelah kiri harus minimal ada sebuah variable.
* |a| lebih dari sama dengan |b|
Bahasa: wirectricked level / tipe 0
Mesin Otomata: Mesin turing.
Aturan :
* simbol ruas sebelah kiri harus minimal ada sebuah simbol variable.
* tidak ada batasan pada aturan produksi.
Tidak ada komentar:
Posting Komentar