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)