BAB I
PENDAHULUAN
1.1 Latar
Belakang Masalah
Mengetahui
apa itu Rege-ex, Klasifikasi chomsky, finite automata.
Regular
Expression atau Regex, merupakan sebuah teknik atau cara untuk mencari
persamaan - persamaan atau mencari string yang di cocokan dengan string
tertentu. Fungsi yang dapat digunakan untuk operasi regex adalah :ereg(string_pola,
string_sumber);. Fungsi ini akan menghasilkan TRUE, jika ternyata pola
cocok dengan sumber dan FALSE jika keduanya tidak cocok.Pola dari fungsi
di atas adalah rumus dari data text yang diinginkan. Finite automata adalah mesin abstrak berupa sistem model matematika dengan
masukan dan keluaran diskrit yang dapat mengenali bahasa paling sederhana (bahasa
reguler) dan dapat diimplementasikan
secara nyata dimana sistem dapat berada disalah satu dari sejumlah berhingga
konfigurasi internal disebut state.
1.2
Tujuan Makalah
Tujuan dari
makalah ini ialah untuk menyelesaikan tugas mata kuliah Teknik Kompilasi
Serta
menambah lmu pengetahuan tentang Rege-ex, klasifikasi chomsky, Finite Automata
Baik untuk penulis maupun para pembaca.
BAB II
LANDASAN TEORI
· Regex (Regular Expression)
Regular Expression atau Regex, merupakan
sebuah teknik atau cara untuk mencari persamaan - persamaan atau mencari string
yang di cocokan dengan string tertentu,dalam php yang paling banyak digunakan
adalah PCRE atau (Perl Compatible
Regular Expressions), penggunaan dari regex sebebenarnya cukup luas, secara
umum digunakan untuk mencari string (kata, huruf, simbol) dalam
kumpulan-kumpulan string, misalnya ada sebuah string "saya pergi
sekolah", dalam string tersebut terdapat beberapa kata, dan kita ingin mencari
beberapa kata dengan kondisi tertentu, misalnya mencari kata dengan awalan P,
atau mencari kata dengan akhiran A atau mencari kata di antara kata “saya” dan
“kata sekolah”, di sinilah regex berperan, untuk mencari string dalam string
dengan patern (kondisi) tertentu.
Awal mula gagasan ekspresi
reguler(Regex) dikemukakan pada tahun 1940 oleh Warren McCulloch dan Walter
Pitts yang memiliki bidang keahlian neuro-physiologist dengan mengembangkan
model sederhana mengenai sistem syaraf pada level neuron. Stephe Kleene
mengemukakan notasi sederhana untuk mengekspresikan himpunan reguler ini
disebut ekspresi reguler(Regex). Pada tahun 1950 dan 1960-an,
ekspresi reguler memperoleh perhatian para matematikawan. Pada tahun 1968, Ken
Thompson menggunakan ekspresi reguler untuk persoalan komputasi, ditulis dalam
makalah berjudul "Reguler Expression Search Algorithm" yang
mendeskripsikan kompilator ekspresi reguler sehingga menghasilkan kode objek
untuk komputer 8094.
Fungsi
Regex
Fungsi yang dapat digunakan untuk operasi
regex adalah :ereg(string_pola,
string_sumber);.
Fungsi ini akan menghasilkan TRUE,
jika ternyata pola cocok dengan sumber dan FALSE jika keduanya tidak cocok.Pola
dari fungsi di atas adalah rumus dari data text yang diinginkan. Cara
membuat rumus canggih ini dengan menggunakan karakter meta. singkatnya meta itu
adalah karakter yang memiliki arti tertentu. contoh pada perintah DOS
adalah DIR *.*, karakter *
tidak diartikan sebagai karakter bintang oleh komputer melainkan mempunyai arti
khusus.
Regex memiliki dua jenis karakter
dasar salah satunya adalah Metakarakter untuk menyatakan teks dapat
bermacam-macam di string target sesuai dengan metakarekter yang digunakan.
Metakarakter pada Regex antara lain :
|
^.....$
|
Tanda awal dan akhir dari sebuah baris
|
|
{.....}
|
Untuk mendefinisikan range
|
|
[.....]
|
Untuk mendefinisikan karakter kelas
|
|
(.....)
|
Untuk mendefinisikan group
|
|
*
|
Untuk menyatakan perulangan minimal 0 kali sampai tak terhingga
|
|
+
|
Untuk menyatakan perulangan minimal 1 kali sampai tak terhingga
|
|
?
|
Untuk menyatakan perulangan minimal 1 kali atau tidak sama
sekali
|
|
|
|
cOperator logika untuk OR
|
|
\
|
Menjadikan karakter setelahnya tidak lagi dianggap sebagai
metcharacter dan hanya akan dianggap sebagai karakter biasa
|
|
\t
|
Merepresentasikan karakter tab
|
|
\n
|
Merepresentasikan karakter newline
|
|
\r
|
Merepresentasikan carriage-return character
|
|
\f
|
Merepresentasikan form-feed character
|
|
\a
|
Merepresentasikan karakter bel
|
|
\e
|
Merepresentasikan karakter espace
|
Disamping itu terdapat juga Kelas
Karakter yang dapat digunakan untuk mencari kesesuaian atau kecocokan karakter
pada pola yang telah ditentukan.
Kelas karakter pada regex sbb :
|
[abc]
|
Hanya a atau b atau c
|
|
[^abc]
|
Semua karakter selain a,b dan c
|
|
[a-zA-Z]
|
Salah satu karakter dari a sampai z
atau dari A sampai Z
|
|
[a-d[m-p]]
|
Salah satu karakter dari hasil
gabungan antara a sampai p, (union =
[a-dm-p])
|
|
[a-z&&[def]]
|
Salah satu karakter dari hasil
irisan a sampai z dan def (intersection
= [def])
|
|
[a-z&&[^bc]]
|
Salah satu karakter dari a sampai z
selain b dan c (substraction = [ad-z])
|
Pada
Regex terdapat juga Kelas karakter yang sudah didefinisikan diantaranya adalah
sbb:
|
-
|
Mewakili semua karakter kecuali line
terminator
|
|
\d
|
Merepresentasikan sebuah angka =
[0-9]
|
|
\D
|
Merepresentasikan selain angka =
[^0-9]
|
|
\s
|
Merepresentasikan karakter
whitespace = [\t\n\f\r\x0B]
|
|
\S
|
Merepresentasikan selain karakter
white space = [^\s]
|
|
\w
|
Merepresentasikan sebuah huruf atau
angka = [a-zA-Z0-9]
|
|
\W
|
Merepresentasikan selain huruf atau
angka =[^\w]
|
Contoh Penggunaan Regex
1.
Validasi Tanggal dengan format
“dd-MM-yyyy”
Ekspresi
Regularnya = “((^0[1-9]{1}|^[12][0-9]|3[01])-(0[1-9]|1[012])-(19|20)\d\d$)”
2.
Validasi IP pada IPV4
Ekspresi
Regularnya =
“^([0-9]{1,2}|(0)[0-9]{1,2}|(1)[0-9]{1,2}|(2)[0-4]?[0-9]?|(2)(5)[0-5]?)\.([0-9]{1,2}|(0)[0-9]{1,2}|(1)[0-9]{1,2}|(2)[0-4]?[0-9]?|(2)(5)[0-5]?)\.([0-9]{1,2}|(0)[0-9]{1,2}|(1)[0-9]{1,2}|(2)[0-4]?[0-9]?|(2)(5)[0-5]?)\.([0-9]{1,2}|(0)[0-9]{1,2}|(1)[0-9]{1,2}|(2)[0-4]?[0-9]?|(2)(5)[0-5]?)$”
3.
Validasi Alamat Email
Ekspresi
Regularnya = “^([A-Za-z0-9]+([_]|[.])?)+[A-Za-z0-9]+\@(([A-Za-z0-9]+[-]?)+[A-Za-z0-9]+\.)+[A-Za-z]{2,3}$”
·
Finite Automata
Finite
automata adalah mesin abstrak berupa sistem model matematika dengan masukan dan
keluaran diskrit yang dapat mengenali bahasa paling sederhana (bahasa reguler) dan dapat
diimplementasikan secara nyata dimana sistem dapat berada disalah satu dari
sejumlah berhingga konfigurasi internal disebut state. State sistem merupakan
ringkasan informasi yang berkaitan dengan masukan-masukan sebelumnya yang
diperlukan untuk menentukan perilaku sistem pada masukan-masukan berikutnya.
Finite Automata menggunakan prosedur yang saat
diberikan masukan "string berhingga" akan berhenti. Finite Automata
menyatakan "ya" dengan sejumlah berhingga komputasi jika string
tersebut merupakan elemen bahasa sehingga lebih berfokus pada pengenalan dimana
bila diberikan suatu program (string) akan menyatakan apakah string tersebut termasuk di bahasa atau tidak.
Model Finite Automata
Model Finite Automata memiliki ciri-ciri:
v Memori 'infinite'-nya adalah null (tidak
ada memori sementara).
v Head hanya bergerak 1 arah.
v Hanya berisi memori masukan berupa
tape berisi string masukan dan sejumlah
kendali
berhingga.
Properti Finite
Automata
Finite
Automata memiliki:
v 1 himpunan state kendali berhingga
v Simbol-simbol masukan yang
dibolehkan/diijinkan
v State mula (initial state)
v Himpunan state akhir (set of final states) state-state yang menandai
diterimanya masukan.
v Fungsi transisi state (state transition function) Adanya fungsi yang
memberikan state saat itu (current state) dan simbol masukan saat itu (current
input symbol). Selain itu juga fungsi memberikan/menyatakan semua state
berikutnya yang dimungkinkan.
Semua kemungkinan transisi dipandang dijalankan secara paralel. Bila terdapat transisi yang menuju/sampai state akhir, berarti string masukan diterima otomata.
Semua kemungkinan transisi dipandang dijalankan secara paralel. Bila terdapat transisi yang menuju/sampai state akhir, berarti string masukan diterima otomata.
Cara Kerja Finite Automata :
Finite Automata bekerja dengan cara mesin membaca memori masukan berupa tape yaitu 1 karakter tiap saat (dari kiri ke kanan) menggunakan head baca yang dikendalikan oleh kotak kendali state berhingga dimana pada mesin terdapat sejumlah state berhingga.
Finite
Automata selalu dalam kondisi yang disebut state awal (initial state) pada saat
Finite Automata mulai membaca tape. Perubahan state terjadi pada mesin ketika
sebuah karakter berikutnya dibaca.
Ketika head
telah sampai pada akhir tape dan kondisi yang ditemui adalah state akhir, maka
string yang terdapat pada tape dikatakan diterima Finite Automata
(String-string merupakan milik bahasa bila diterima Finite Automata bahasa
tersebut).
Implementasi Finite Automata
Sistem dengan state
berhingga diterapkan pada:
v Sistem elevator
v Mesin pengeluar minuman kaleng (vending machine)
v Pengatur lampu lalu lintas (traffic light regulator)
v Sirkuit penyaklaran (switching) di komputer dan telekomunikasi
v Protokol komunikasi (communication protocol)
v Analisis Leksikal (Lexical analyzer)
v Neuron nets
v sistem Komputer
Finite State Diagram (FSD)
Perilaku Finite Automata
dimodelkan dengan Finite State Diagram (FSD) dapat juga disebut State
Transition Diagram.
Finite State Diagram terdiri dari:
1. Lingkaran menyatakan stateLingkaran
diberi label sesuai dengan nama state
tersebut.
Adapun pembagian lingkaran adalah:
Adapun pembagian lingkaran adalah:
v Lingkaran bergaris tunggal berarti state sementara
v Lingkaran bergaris ganda berarti state akhir
2. Anak Panah menyatakan transisi
yang terjadiLabel di anak panah menyatakan simbol yang membuat transisi
dari 1 state ke state lain 1 anak panah diberi label start untuk
menyatakan awal mula transisi dilakukan
Contoh :
Gambar dibawah menggambarkan perilaku FA untuk penerimaan bilangan nyata (riil) yang paling tidak mempunyai 1 digit setelah titik desimal adalah sebagai berikut:
Simpul-simpul (berbentuk lingkaran) pada FSD dibawah mengambarkan state-state dari FA, yaitu :
v Simpul S
v Simpul A
v Simpul B
Busur dari 1 simpul ke simpul lainn menandakan transisi state. Karakter samping atau diatas busur menandakan karakter yang menyebabkan terjadinya transisi state.Simpul dengan garis ganda menunjukkan state akhir.Digit adalah nilai 0,1,2,3,4,5,6,7,8,9
Gambar: FSD
Bilangan Nyata Dengan Minimal Satu Angka di Belakang Titik Desimal
Contoh string : 9.8765
v Busur berlabel StartMenunjukkan transisi ke state S
v Head membaca nilai “9”Terdapat kondisi yang menunjukkan
kesesuaian dengan aturan kendali pada state S yaitu adanya busur yang
menunjukkan digit kembali ke state S (berarti memiliki kesesuaian bahasa)
v Pembacaan ke karakter berikutnya adalah "." Terdapat kesesuaian dengan aturan
kendali pada state S, yaitu adanya busur yang menunjukkan nilai "."
ke state A (kondisi berada di state A)
v Pembacaan karakter berikutnya =“8”Terdapat kesesuaian dengan aturan kendali yang sekarang sudah
berada di state A, yaitu busur ke state B yang menunjukkan digit (kondisi
berada di state B)
v Pembacaan karakter berikutnya = “7”Terdapat kesesuaian dengan aturan kendali pada state B, yaitu
adanya busur yang menunjukkan digit kembali ke state B (kondisi tetap berada di
posisi B)
v Pembacaan karakter berikutnya = “6”Terdapat kesesuaian dengan aturan kendali pada state B, yaitu
adanya busur yang menunjukkan digit kembali ke state B (kondisi tetap berada di
posisi B)
v Pembacaan karakter berikutnya = “5”Terdapat kesesuaian dengan aturan kendali pada state B, yaitu
adanya busur yang menunjukkan digit kembali ke state B (kondisi tetap berada di
posisi B)
v Penyesuaian aturan kendali pada akhir pembacaan dilakukan
penyesuaian apakah karakter terakhir berada pada state akhir.
Bila kesesuai kondisi “YA” maka string termasuk di dalam bahasa, dalam hal ini karakter "5" berada pada state B yaitu state dengan lingkaran bergaris ganda yang
menandakan
state akhir, maka sesuai. String 9.8765
termasuk di dalam bahasa Finite Automata pada FSD di atas.
Contoh string : a
v
Busur berlabel StartMenunjukkan
transisi ke state S
v
Head membaca
nilai “a”Terdapat kondisi yang
menunjukkan ketidaksesuaian dengan aturan kendali pada state S yaitu tidak
adanya busur yang menunjukkan persamaan simbol dengan simbol yang dibaca
("a")
v
Ketidaksesuaian
simbol aturan kendali pada kondisi "TIDAK"
menandakan string a tidak termasuk di dalam bahasa FSD di atas
Klasifikasi
Finite Automata
Finite
automata dapat berupa:
v Deterministic Finite Automata (DFA) terdiri dari 1 transisi dari
suatu state pada 1 simbol masukan.
v Nondeterminictic Finite Automata (NDFA) Lebih dari 1 transisi dari
suatu state dimungkinkan pada simbol masukan yang sama
Kedua finite automata tersebut mampu mengenali himpunan reguler secara presisi. Dengan demikian kedua finite automata itu dapat mengenali string-string yang ditunjukkan dengan ekspresi reguler secara tepat. DFA dapat menuntun recognizer(pengenal) lebih cepat dibanding NDFA. Namun demikian, DFA berukuran lebih besar dibanding NDFA yang ekivalen dengannya. Lebih mudah membangun NDFA dibanding DFA untuk suatu bahasa, namun lebih mudah mengimplementasikan DFA diabnding NDFA.
Kedua finite automata tersebut mampu mengenali himpunan reguler secara presisi. Dengan demikian kedua finite automata itu dapat mengenali string-string yang ditunjukkan dengan ekspresi reguler secara tepat. DFA dapat menuntun recognizer(pengenal) lebih cepat dibanding NDFA. Namun demikian, DFA berukuran lebih besar dibanding NDFA yang ekivalen dengannya. Lebih mudah membangun NDFA dibanding DFA untuk suatu bahasa, namun lebih mudah mengimplementasikan DFA diabnding NDFA.
BAB III
PENUTUP
3.1 Kesimpulan
Kesimpulannya adalah Regular
Expression atau Regex, merupakan sebuah teknik atau cara untuk mencari
persamaan - persamaan atau mencari string yang di cocokan dengan string
tertentu.
Fungsi yang dapat digunakan untuk operasi regex adalah :ereg(string_pola,
string_sumber);.
Fungsi ini akan menghasilkan TRUE, jika
ternyata pola cocok dengan sumber dan FALSE jika keduanya tidak cocok.Pola dari
fungsi di atas adalah rumus dari data text yang diinginkan.
Finite automata adalah
mesin abstrak berupa sistem model matematika dengan masukan dan keluaran
diskrit yang dapat mengenali bahasa paling sederhana (bahasa reguler) dan dapat diimplementasikan secara
nyata dimana sistem dapat berada disalah satu dari sejumlah berhingga konfigurasi
internal disebut state.
Model Finite Automata memiliki ciri-ciri:
v Memori 'infinite'-nya adalah null (tidak
ada memori sementara).
v Head hanya bergerak 1 arah.
v Hanya berisi memori masukan berupa
tape berisi string masukan dan sejumlah
kendali
berhingga.
3.2 SARAN
Sebaiknya kita
lebih memahami lagi tentang apa itu regex, klasifikasi chomsky, dan finite
automata agar lebih menambah pengetahuan. Mungkin hanya ini
yang dapat kami wacanakan pada penulisan kelompok ini meskipun penulisan ini
jauh dari sempurna mudah-mudahan dapat bermanfaat bagi kita semua.
Referensi
Tidak ada komentar:
Posting Komentar