78 lines
3.0 KiB
Python
78 lines
3.0 KiB
Python
import sys
|
|
|
|
def read_aut_nfa(nfsa_path):
|
|
with open(nfsa_path, "r", encoding="utf8") as file:
|
|
transisions = {}
|
|
accepting_states = set()
|
|
for line in file:
|
|
if line.startswith("#"):
|
|
continue
|
|
parts = line.strip().split()
|
|
if len(parts) == 1:
|
|
accepting_states.add(int(parts[0]))
|
|
else:
|
|
state_from = int(parts[0])
|
|
state_to = int(parts[1])
|
|
#symbol = ' ' if len(parts) == 2 else parts[2]
|
|
symbol = parts[2] if len(parts) == 3 else "<eps>"
|
|
if(state_from, symbol) not in transisions:
|
|
transisions[(state_from, symbol)] = []
|
|
transisions[(state_from, symbol)].append(state_to)
|
|
#print(transisions)
|
|
return transisions, accepting_states
|
|
|
|
|
|
def is_accepted_byNFA(transisions, accepting_states, line):
|
|
current_states = set([0])
|
|
for symbol in line.strip():
|
|
#print(f"Obecny symbol: {symbol}")
|
|
next_states = set()
|
|
for state in current_states:
|
|
if (state, symbol) in transisions:
|
|
next_states.update(transisions[(state,symbol)])
|
|
#print(next_states)
|
|
#print(f"Przejście przez '{symbol}' ze stanu {state}: {transisions[(state, symbol)]}")
|
|
if len(next_states) == 0:
|
|
for state in current_states:
|
|
if (state, "<eps>") in transisions:
|
|
next_states.update(transisions[(state, "<eps>")])
|
|
#print(next_states)
|
|
#print(f"Epsilonowe przejście ze stanu {state}: {transisions[(state, '<eps>')]}")
|
|
|
|
if len(next_states) == 0:
|
|
#print("Brak dostępnych przejść")
|
|
return "FALSE"
|
|
current_states = next_states
|
|
#print(f"Obecny stan po przejsciu petli ------------------------------------------------ '{symbol}': {current_states}")
|
|
|
|
#print(current_states)
|
|
#kod powyżej nie uwzględni epsilonowych przejść na końcu słowa. Tutaj to uwzględniam
|
|
flaga = True
|
|
while flaga:
|
|
flaga = False
|
|
next_states = set()
|
|
for state in current_states:
|
|
if(state, "<eps>") in transisions:
|
|
next_states.update(transisions[(state, "<eps>")])
|
|
flaga = True
|
|
current_states = next_states
|
|
|
|
if any(state in accepting_states for state in current_states):
|
|
return "TRUE"
|
|
else:
|
|
return "FALSE"
|
|
|
|
def process_input(transisions, accepting_states, input_file, output_file):
|
|
with open(input_file, "r") as input, open(output_file, "w") as output:
|
|
for line in input:
|
|
result = is_accepted_byNFA(transisions, accepting_states, line)
|
|
output.write(result + ' ' + line)
|
|
|
|
|
|
|
|
|
|
|
|
nfa_file, input_file, output_file = sys.argv[1], sys.argv[2], sys.argv[3]
|
|
transisions, accepting_states = read_aut_nfa(nfa_file)
|
|
|
|
process_input(transisions, accepting_states, input_file, output_file) |