Write a basic python program to simulate a finite automata. The automata examples are from Siper's book. program:

class SimpleFiniteAutomata: def __init__(self,fa_description): self.fa = fa_description self.state = self.fa['start'] def one_step(self,symbol): """ takes a symbol (a string) and returns a state it is the state arrived at given the symbol at the current state """ # write code here return self.state # do not take this as a hint def compute(self,string):

""" takes a string and put the FA in the start state, then applies one_step to each symbol in the string. returns True if the FA ends in an accepting state; else returns False """ # write code here return False # do not takes this as a hint

#end class SimpleFiniteAutomata

--------------- test to check work: def simple_fa_test(fa_desc,test_vect,verbose=False): fa = SimpleFiniteAutomata(fa_desc) tv_true, tv_false = test_vect correct = 0

for string in tv_true: if fa.compute(string): correct += 1 for string in tv_false: if not fa.compute(string): correct += 1 return (correct,len(test_vect[0]) + len(test_vect[1]))

fa_all = [ ('M1',m1,m1_test), ('M2',m2,m2_test), ('M3',m3,m3_test), ('M4',m4,m4_test), ]

for fa in fa_all: correct, total = simple_fa_test(fa[1],fa[2]) print(f' Machine {fa[0]}: {correct} correct out of {total} tests.')

--- example of a Finite Automata Description. # this one is M1, from figure 1.4 in Sipser

m1 = { 'states':{'q1','q2','q3'}, 'alphabet':{'0','1'}, 'transitions':{ ('q1','0'):'q1', ('q1','1'):'q2', ('q2','1'):'q2', ('q2','0'):'q3', ('q3','0'):'q2', ('q3','1'):'q2' }, 'start':'q2', 'accept':{'q2'} }

m1_test = (["1","01","11","0101010101","100","0100","010000"],["0","10","101000"])