pengenal token - wordpress.com · web viewc. fungsi transisi pindah (move) untuk memetakan pasangan...

Teknik Kompilasi 04 / 1 - 14

FINITE AUTOMATA(OTOMATA BERHINGGA)

NON DETERMINISTIC FINITE AUTOMATA (NFA)

Model Matematika terdiri dari :a. Himpunan state dinyatakan dengan Sb. Himpunan simbol input (alfabet sim-

bol) dinyatakan dengan c. Fungsi transisi pindah (move) untuk

memetakan pasangan state-simbol ke himpunan state.

d. State S0 disebut sebagai state awal.e. Himpunan state F disebut sebagai

state penerima (accepting state)

Diagram Transisi (representasi NFA) simbol input yang sama bisa melabeli dua atau lebih transisi yang keluar dari

Bahan Ajar Matakuliah oleh SINAR SINURAT


state yang sama dan simbol meng-gambarkan transisi kosong.

DETERMINISTIC FINITE AUTOMATA(DFA)

a. Tidak ada peralihan atas input εb. Setiap state S dan simbol input a,

paling banyak satu sisi dengan label input a yang meninggalkan S

KEUNTUNGAN DAN KERUGIAN

1. DFA lebih cepat menghasilkan suatu pengenal

2. Ukuran DFA lebih besar daripada NFA untuk mengenal RE yang sama

Contoh : Bahasa menerima RE : (a | b)* abb

Diagram Transisi pada DFA :



Diagram Transisi pada NFA

S = { 0,1,2,3} adalah Himpunan State = {a,b} adalah alfabet simbol inputS0= {0} ; F = {3}



Implementasi fungsi peralihan NFA di-gunakan Tabel Translasi (Translation Table)

State Input Symbol

a b0 {0,1} {0}1 - {2}2 - {3}

KONVERSI RE KE NFA

Merupakan salah satu strategi untuk membentuk sebuah pengenal dari sebuah RE

Algoritma : Thompson’s Construction Input : RE r pada alfabet Output : NFA N yang menerima L(r) Metode:

Menguraikan r menjadi sub-expression



Gunakan aturan (1) dan (2) berikut untuk membentuk NFA untuk setiap simbol dasar dari r (meru-pakan simbol alfabet atau )

NFA tersebut dikombinasikan secara induksi dengan menggu-nakan aturan (3) berikut.

Aturan : 1) Untuk , dibentuk NFA :

start ε

Dimana : i : start state yang baru f : accepting state yang baru NFA ini mengenal {} 2) Untuk a di dalam , bentuk NFA :

start a

Dimana : i : start state yang baru

f : accepting state yang baru NFA ini mengenal {a}


i f

i f


3) Misalkan N(s) dan N(t) adalah NFA untuk regular expression s dan t :

a) Untuk RE (s|t) bentuk NFA gabungan N(s|t)

Dimana : i : start state yang baru

f : accepting state yang baru NFA ini mengenali L(s) L(t)

b) Untuk RE st, bentuk NFA gabungan N(st)

Dimana :- Start state N(s) menjadi start state

NFA gabungan- Accepting state N(t) menjadi accept-

ing state dari NFA gabungan


i

i f

N(s)

N(t)

start

fstart N(s) N(t)


- NFA ini mengenali L(s) L(t)

(c) Untuk RE s*, bentuk NFA gabungan N(s)*.

Dimana :i : start state yang baruf : accepting state yang baru

NFA ini mengenali (L(s))*(d) Untuk RE didalam kurung: (s),

gunakan N(s) itu sendiri sebagai NFA yang baru.

Algoritma di atas menghasilkan sebuah NFA N(r) yang memiliki sifat-sifat sebagai berikut :


N(s)i fstart


1. N(r) mempunyai state paling banyak dua kali jumlah simbol dan operator di dalam r.

2. N(r) mempunyai tepat satu start state dan satu accepting state. Accepting state tidak memiliki transisi ke luar.

3. Setiap state di N(r) mempunyai satu transisi keluar untuk sebuah simbol di dalam atau paling banyak dua transisi keluar untuk simbol (transisi ).



Contoh :Berdasarkan algoritma tersebut bentuk NFA N(r) dari RE : (a | b)* abb

a start a b b

b

KONVERSI RE KE DFA

Strategi pembuatan DFA dari RE dengan mengikuti aturan berikut : Augmental RE r# Dibuat pohon sintaks dari Augmental

RE r dan posisinya


0 1 6 7 8 9 10

2 3

4 5


RE Syntax treea | b

ab

a* dan a+

| a b a b * + a dan a

Rules untuk menentukan nullable, firstpos, lastpos



Node n Nullable (n) Firstpos (n) Lastpost (n)Jika n=leaf dilabeli

True Ø Ø

Jika n=leafdilabeli i

False { i } { i }

n |

C1 c2

Nullable(c1)

Nullable(c2)

Firstpos(c1)

Firstpos(c2)

Lastpos(c1)

Lastpos(c2) n

c1 c2

Nullable(c1)

Nullable(c2)

If nullable(c1)

ThenFirstpos(c1)

Firstpos(c2)

ElseFirstpos(c1)

If nullable(c2)

ThenFirstpos(c1)

Firstpos(c2)

ElseFirstpos(c2)

n

True Firstpos(c1) Lastpos(c1)

Rules untuk menentukan followpos1. Jika n adalah cat-node left-child c1

dan right-child c2, dan i adalah posisi dalam lastpos (c1) maka semua posisi dalam lastpos (c2) adalah followpos ( i )


C2


2. Jika n adalah node start dan i adalah posisi dalam lastpos (n) maka semua posisi dalam firstpos (n) adalah dalam followpos (i)

Contoh :Berdasarkan algoritma di atas bentuk DFA dari RE : r = (a | b)* abb

Maka augmental RE r# r = ( ab ) * abb#

Pohon sintaks untuk firstpost, lastpos :


1 2 3 4 5 6

{1} {1} {2} {2}

{1,2} {1,2}

{1,2} {1,2} {3} {3}

{1,2,3}

{3}

{4}

{4}

{4}

{1,2,3}

{1,2,3}

{1,2,3}

{5}

{5}

{5}

{6}

{6}

{6}

# F

b F

b F

a F

*

aF

bF

F

F

T

F

F

F

Jadi Root yang diperoleh dari pohon sintaks adalah {1,2,3} = A


Penomoran posisi hanya pada leaf dan dimulai dari kiri bawah (depth-left-first)

Pohon sintaks untuk Folowpos (n) : Himpunan posisi semua simbol terletak pada sesudah symbol pada posisi n

Node Followpos123456

{1,2,3}{1,2,3}

{4}{5}{6}-

Digraph untuk fungsi followpos :

13 4 5 6

2


2

3 4 5 6


State Input a B

followpos (1) followpos (2) A Followpos(3) = = {1, 2, 3} = A{1,2,3} {1, 2, 3, 4} = B

Followpos (1) followpos (2) B Followpos (3) followpos (4)

{1,2,3,4} = {1,2, 3, 4} = B = {1, 2, 3, 5} = CFollowpos (1) followpos (2)

C Followpos (3) followpos (5){1,2,3,5} = {1, 2, 3, 4 } = B = {1, 2, 3, 6} = D

Followpos (1) followpos (2)D Followpos (3) = {1, 2, 3 } =A

{1,2,3,6} = {1, 2, `3, 4} = B

Maka bentuk DFA nya adalah:

b b start a b b

a a a


B A D

C

pengenal token - wordpress.com · web viewc. fungsi transisi pindah (move) untuk memetakan pasangan...

Documents