jfz-2023-s464983/TaskC04/run.py
2023-12-09 21:52:30 +01:00

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)