Bahasa Regular : Ekspresi Regular, Aturan Produksi dan Pohon Penurunan.

Ekspresi Leguler

Sebuah bahasa dinyatakan regular jika terdapat finite state automata yang dapatmenerimanya. bahasa yang diterima oleh suatu finite state automata bisa dinyatakan secara sederhana dengan ekspresi regular (regular expression).

• Ekspresi regular selanjutnya kita sebut sebagai ER, memungkinkan menspesifikasikanatau mendefinisikan Bahasa-bahasa.
• Ekspresi regular memberikan suatu pola (pattern) atau template untuk untai / string dari suatu bahasa.
• Untai yang menyusun suatu bahasa regular akan cocok (match) dengan pola bahasaitu.

ATURAN PRODUKSI TATA BAHASA REGULER

Suatu tata bahasa (grammar) didefinisikan dengan 4 Tupel yaitu : V, T, P, dan S

Di mana,

V = Himpunan simbol variabel / non terminal

T = Himpunan simbol terminal

P = Kumpulan aturan produksi

S = Simbol awal

Pohon Penurunan

Sebuah pohon (tree) adalah suatu graph terhubung tidak sirkuler, yang memiliki satusimpul(node) vertex disebut akar (root) dan dari situ memiliki lintasan ke setiapsimpul.Pohon sintaks / pohon penurunan (syntax tree/derivaton tree/parse tree) bergunauntukmenggambarkan bagaimana memperoleh suatu string (untai) dengan cara menurunkansimbol-simbol variabel menjadi simbol-simbol terminal. Setiap simbol variable diturunkan menjadi terminal, sampai tidak ada yang belum tergantikan.