RE to DFA

1. Tambahkan augmented variable (#) di akhir expression
2. Tambahkan konkatenasi (.) pada expression (. ditambahkan diantara variabel yang tidak memiliki |)
3. Beri nomor pada setiap variabel
4. Tentukan nilai followpos(ition)
5. Buat tree (kumpulan node)
   • Node -> O (lingkaran)
   • Variabel/Leaf -> tidak punya tangan
   • Simbol -> 2 tangan (. atau |)
   • Closure -> 1 tangan (*, +, atau ?)
6. Beri nomor pada leaf (paling bawah)
7. Tentukan nilai firstpos, lastpos, dan nullable
8. Buatlah tabel DFA
   • firstpos paling atas adalah S0 (start) pada DFA
   • isi dari variabel (a) adalah gabungan followpos variabel (fp (1,3) -> 1,2,3,4)
   • jika ada angka dari # maka final state

Followpos

(a|b)*a#
 1 2  34

followpos 1 --> aa, ab, aba, aaa
				11  12  123  113 --> ada 1, 2, 3 (followpos 1 adalah 1, 2, 3)

followpos 2 --> bb, ba, ba, baa
			    22  21  23  213 --> ada 1, 2, 3 (followpos 2 adalah 1, 2, 3)

followpos 3 --> # 
			   4 --> followpos 3 adalah 4

followpos 4 --> -
				- --> tidak ada
				

Firstpos

firstpos -> angka pada depan node

• leaf -> sesuai angka leaf
• simbol | -> gabungan firstpos node depan (1) dan belakang (2) -> 1,2
• simbol . -> jika nullable node _depan_ FALSE, firstpos depan, else gabungan
• closure -> sesuai bawahnya

Lastpos

lastpos -> angka pada belakang node

• leaf -> sesuai angka leaf
• simbol | -> gabungan lastpos node depan (1) dan belakang (2) -> 1,2
• simbol . -> jika nullable node _belakang_ FALSE, lastpos belakang, else gabungan
• closure -> sesuai bawahnya

Nullable

nullable -> node bisa bernilai null atau tidak (TRUE|FALSE)

• leaf -> pasti FALSE kecuali empty
• simbol | -> TRUE jika _salah satu_ node bawah TRUE, else FALSE
• simbol . -> TRUE jika _kedua_ node bawah TRUE, else FALSE
• closure *, ? -> pasti TRUE, bisa menghasilkan empty
• closure + -> sesuai bawahnya

Ex