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.