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

Cara 1: Menggunakan Tree

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

Cara 2: Thompson’s Construction

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 = ɸ

www.binus.ac.id