Source Code Deterministic Finite Automaton (DFA) Menggunakan Python

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

 

Bagikan: