46 lines
1.7 KiB
Python
46 lines
1.7 KiB
Python
class FiniteAutomata:
|
|
def __init__(self, file_path):
|
|
self.alphabet = set()
|
|
self.states = set()
|
|
self.transitions = {}
|
|
self.start_state = None
|
|
self.final_states = set()
|
|
self.read_fa(file_path)
|
|
|
|
def read_fa(self, file_path):
|
|
with open(file_path, "r") as file:
|
|
self.states = set(file.readline().strip().split())
|
|
self.alphabet = set(file.readline().strip().split())
|
|
self.start_state = file.readline().strip()
|
|
self.final_states = set(file.readline().strip().split())
|
|
for line in file:
|
|
state1, state2, char = line.strip().split()
|
|
if state1 not in self.transitions:
|
|
self.transitions[state1] = {}
|
|
if char not in self.transitions[state1]:
|
|
self.transitions[state1][char] = []
|
|
self.transitions[state1][char].append(state2)
|
|
|
|
def is_accepted(self, word):
|
|
current_states = [self.start_state]
|
|
for char in word:
|
|
new_states = []
|
|
for state in current_states:
|
|
if state in self.transitions and char in self.transitions[state]:
|
|
new_states.extend(self.transitions[state][char])
|
|
current_states = new_states
|
|
return any(state in self.final_states for state in current_states)
|
|
|
|
def isNFA(self):
|
|
for state in self.transitions:
|
|
for char in self.transitions[state]:
|
|
if len(self.transitions[state][char]) > 1:
|
|
return True
|
|
return False
|
|
|
|
|
|
fa = FiniteAutomata("FA.in")
|
|
print(fa.isNFA())
|
|
print(fa.is_accepted("1312"))
|
|
print(fa.is_accepted("12321"))
|
|
print(fa.is_accepted("")) |