TM1 Teknik Kompilasi

Posted March 9th, 2014 by agungroyat

RE :  a*(b|cd)*(a|b)#

Cara 1 :

Followpos 1        :               1 , 2, 3, 5, 6
Followpos 2        :               2, 3, 5, 6
Followpos 3        :               4
Followpos 4        :               2, 3, 5, 6
Followpos 5        :               7
Followpos 6        :               7
Followpos 7        :               –

S0 = 1, 2, 3, 5, 6

State	a	b	c	d
S0 = 1, 2, 3, 5, 6	1, 2, 3, 5, 6, 7 = S1*	2, 3, 5, 6, 7 = S2*	4 = S3	–
S1*	S1*	S2*	S3	–
S2*	7 = S4*	S2*	S3	–
S3	–	–	–	2, 3, 5, 6 = S5
S4*	–	–	–	–
S5	S4*	S2*	S3	–

Maka hasil DFAnya ialah :

DFA tersebut tidak dapat diminimisasi lagi.

Cara 2 : 

S0 ɛ closure = (0, 1, 3, 4, 5, 6, 11, 12, 14)

S0,a = (2, 13)           ɛ closure = (1, 2, 3, 4, 5, 7, 11, 12 ,14, 16) –> S1*
S0,b = (6, 15)          ɛ closure = (4, 5, 7, 10 ,11, 12 14, 16) –> S2*
S0,c = (8)                  ɛ closure = (ɸ) –> S3
S0,d = ɸ

S1,a = (2, 13) –> S1
S1,b = (6,15) –> S2*
S1,c = (8) –> S3
S1,d = ɸ

S2,a = (13)               ɛ closure (16) –> S4*
S2,b = (6, 15) –> S2*
S2,c = (8) –> S3
S2,d = ɸ

S3,a = ɸ
S3,b = ɸ
S3,c = ɸ
S3,d = (9)                  ɛ closure (10, 11, 12, 14) –> S5

S4,a = ɸ
S4,b = ɸ
S4,c = ɸ
S4,c = ɸ

S5,a = (13) –> S4
S5,b = (15) –> S2
S5,c = (8) –> S3
S5,c = ɸ

Maka hasil DFAnya:

Link Binus Website