Deskripsi
Pengecekan regex menggunakan DFA
Regex: (a|b)a+b
Gambar transition diagram bisa dibuat dihttp://hokein.github.io/Automata.js/#
Source Code
# pythonindo.com
# Subject : regex check using DFA
# transitional state of regex (a|b)a+b
# state 0, 1, 2, 3, 4
# state 4 is final state
dfa = {0:{'a':1, 'b':2},
1:{'a':3},
2:{'a':3},
3:{'b':4, 'a':3}}
def accepts(transitions,initial,accepting,s):
# function to check accepting value
state = initial
for c in s:
try:
state = transitions[state][c]
except KeyError:
return False
return state in accepting
infile = open(r'.\infile.txt')
outfile = open(r'.\outfile.txt','w')
for line in infile.readlines():
line = line.rstrip() # remove \n char
acc_or_reject = 'Accepted' if accepts(dfa, 0, {4}, line) else 'Rejected'
print(line, '->', acc_or_reject ,file=outfile)
infile.close()
outfile.close()
Readme
- Program menggunakan python versi 3
- Letakkan file infile.txt dalam folder yang sama dengan program
- Program bisa dijalankan dari command line dengan sintaks:
python dfa.py - Inputnya adalah file infile.txt dan hasilnya adalah file outfile.txt
Contoh file infile.txt
a b ab aba abaa abba aab baa aaab baab aaaab baaab
Download semua file dalam bentuk zip di sini