0

EKSPRESI REGULER

Posted by Jujur Sitanggang on 5:34 AM



o   Sebuah bahasa dinyatakan regular jika terdapat finite state automata yang dapat menerimanya.
o   Bahasa-bahasa yang diterima oleh FSA bisa dinyatakan secara sederhana dengan ekspresi regular (regular expression).
o   Ekspresi regular memberikan suatu pola (pattern) atau template untuk untai/string dari suatu bahasa.
o   Banyak masalah pada perangkat lunak yang bisa disederhanakan dengan melakukan pengubahan notasi ekspresi regular ke dalam implementasi komputer dari FSA yang bersangkutan.
o   Contoh : Finite State Automata untuk mengenal bilangan bulat /integer tidak bertanda



 



o   Ekspresi Regularnya adalah : misal 0..9 disimbolkan sebagai digit, maka ERnya adalah : (digit)(digit)*

V.1. Notasi Ekspresi Regular
Notasi yang digunakan untuk ER adalah :
1.    * : berarti bisa tidak muncul, bisa juga muncul berhingga kali (0-n)
2.    + : berarti minimal muncul satu kali (1-n)
3.    + : berarti union atau bisa diganti dengan notasi U
4.    .  : berarti konkatenasi, biasanya tanpa ditulis titiknya, misal ab sama  dengan a.b
Contoh ekspresi regular (ER) :
1.    ER : ab*cc
Contoh string yang bisa dibangkitkan abcc, acc, abbcc, abbbcc, dst. (b bisa tidak muncul atau muncul sejumlah berhingga kali)
2.    ER : 010*
Contoh string yang bisa dibangkitkan 01,010, 0100,01000, dst. (0 bisa tidak muncul atau muncul sejumlah berhingga kali)
3.    ER : a+d
Contoh string yang bisa dibangkitkan ad,aad, aaad,aaaad dst. (a minimal muncul satu kali)
V.2. Hubungan ER dengan FSA
o   Untuk setiap ER ada satu NFA dengan transisi ε (NFA ε-move) yang ekivalen.Sementara untuk setiap DFA ada satu ER dari bahasa yang diterima oleh DFA.
o Hubungannya dapat digambarkan sebagai berikut 




0 Comments

Copyright Jujur Soaloon Sitangang Lipan All rights reserved. Theme by Sitanggang. | Bloggerized by Soalparna.