nfa.py

class FA:

def $\_\_$init$\_\_($self$,$ alphabet, states, transition, accepting$\_$states$)$:

self.alphabet $=$ alphabet

self.states $=$ states

self.transition $=$ transition

self.accepting$\_$states $=$ accepting$\_$states

def DFA$($input$\_$string, dfa$)$:

# set current$\_$state to initial state

current$\_$state $=$ dfa.states$[0]$

# run through the input string

for symbol in input$\_$string:

i $=$ dfa.states.index$($current$\_$state$)$

j $=$ dfa.alphabet.index$($symbol$)$

current$\_$state $=$ dfa.transition$[$i$][$j$]$

return current$\_$state

def NFA$($input$\_$string, nfa$)$:

# set current$\_$state to initial state

current$\_$states $=$ #

# run through the input string

for symbol in input$\_$string:

x $=$ set$()$

for state in current$\_$states:

i $=$ nfa.states.index$($state$)$

j $=$ nfa.alphabet.index$($symbol$)$

x $=$ #

current$\_$states $=$ x

return current$\_$states

def main$()$:

# Read in the input$\_$string

input$\_$string $=$ input$()$

# Define a DFA

dfa$1=$ FA$([\text{'}0\text{'},\text{'}1\text{'}],[\text{'}$q$\text{'},\text{'}$r$\text{'}],[[\text{'}$r$\text{'},\text{'}$q$\text{'}],[\text{'}$q$\text{'},\text{'}$r$\text{'}]],\{\text{'}$q$\text{'}\})$

# Define the NFA given in Figure $8\mathrm{.}2$ for n$=5$

nfa$1=$ #

# Run the DFA on the input string

# final$\_$state $=$ DFA$($input$\_$string, dfa$1)$

# if final$\_$state in dfa$1.$accepting$\_$states:

# print$("$Accept$")$

# else:

# print$("$Reject$")$

# Run the NFA on the input string

final$\_$states $=$ NFA$($input$\_$string, nfa$1)$

if set$($final$\_$states$)$ & set$($nfa$1.$accepting$\_$states$)$:

print$("$Accept$")$

else:

print$("$Reject$")$

if $\_\_$name$\_\_=="\_\_$main$\_\_"$:

main$()$