Question

In either Java or Python 3, write a program that simulates a deterministic FSM. It will read from two input files. The first is a file describing an FSM The first line contains the alphabet as a series of characters separated by a single space - The second line contains the number of states as an integer k 2 1; states will be numbered 0,1,..., k -1. The start state is always state O The third line contains a series of integers separated by a single space representing the accepting states -The remaining lines contain information defining δ, the transition function. Each line contains a state number i, a character c from the alphabet, and a state number j. This means that the transition is from state i to state j on character c For example, here's the input describing the FSM that accepts the language {w e sa,b)*: |wl- 0 mod 5): 1 a 2 1 b 2 2 a 3 2 b 3 3 a 4 3 b 4 4 b 0 And here's one for the machine that accepts the language from problem 6 of assignment 2: 4 0 0 1 102 11θ 202 2 1 3 зез 3 1 3 Write the program so that it always reads from a file called fsm.txt. Once the program reads in and processes the FSM input, it will process input strings. These will be in a single file called strings.txt. Each line of this file contains a string. Your program will read each, run it through the FSM, and then print it and whether it was accepted Call the program fsm.(java,py) and submit it through D2L

Answer 1

Code:

def read_fsm(filename):
    fh = open(filename,'r')
    contents = fh.readlines()
    sigma = list(contents[0].rstrip().split(' '))
    table = {}
    n = int(contents[1])
    for i in range(n):
        table[i] = {}
    final = list(map(int,contents[2].rstrip().split(' ')))
    
    for line in contents[3:]:
        fro,ip,to = line.split(' ')
        fro = int(fro)
        to = int(to)
        table[fro][ip] = to
    print(table)
    fh.close()
    return table,final
    
def runString(table,final,string):
    current = 0
    for i in string:
        current = table[current][i]
    if current in final:
        print(string,'--> ACCEPT')
    else:
        print(string,'--> REJECT')
        
def readInput(table,final):
    fh = open('Strings.txt','r')
    for line in fh.readlines():
        string = line.rstrip()
        runString(table,final,string)
    fh.close()
    
def main():
    table,final = read_fsm('fsm.txt')
    readInput(table,final)
    
main()
    

Output:

a REJECTED b --> REJECTED ab -REJECTED ba --REJECTED aab --> REJECTED bba --> REJECTED aba -REJECTED abab -->REJECTED aaab --> REJECTED bbaa --> REJECTED aabbb --> ACCEPTED abbbb --ACCEPTED aaabb --> ACCEPTED aaaab - ACCEPTED ababab -> REJECTED abababa > REJECTED abababab ->REJECTED ababababa -->REJECTED abbababbab --> ACCEPTED abababababa --> REJECTED --> ACCEPTED