import json
from collections import defaultdict


class Errors:
    E1 = 'E1: A state \'{}\' is not in set of states'
    E2 = 'E2: Some states are disjoint'
    E3 = 'E3: A transition \'{}\' is not represented in the alphabet'
    E4 = 'E4: Initial state is not defined'
    E6 = 'E6: FSA is nondeterministic'


def make_array():
    return defaultdict(lambda: defaultdict(lambda: defaultdict(lambda: '{}')))


class FSARegexTranslator:
    def __init__(self, fsa):
        self.fsa = fsa

    def translate(self):
        dp = make_array()
        for i in self.fsa.states:
            for a, j in self.fsa.matrix[i].items():
                if dp['#'][i][j] == '{}':
                    dp['#'][i][j] = a
                else:
                    dp['#'][i][j] += '|{}'.format(a)

            if dp['#'][i][i] != '{}':
                dp['#'][i][i] += '|eps'

        for ki in range(len(self.fsa.states)):
            for i in self.fsa.states:
                for j in self.fsa.states:
                    k = self.fsa.states[ki]
                    if ki > 0:
                        kp = self.fsa.states[ki - 1]
                    else:
                        kp = '#'

                    dp[k][i][j] = \
                        '({})'.format(dp[kp][i][k]) + \
                        '({})*'.format(dp[kp][k][k]) + \
                        '({})'.format(dp[kp][k][j]) + \
                        '|' + \
                        '({})'.format(dp[kp][i][j])


        regexs = [dp[self.fsa.states[-1]][self.fsa._initial][f] for f in self.fsa._final]
        return '|'.join(regexs) if regexs else '{}'



class FSA:
    def __init__(self, states, alphabet, initial, final, transitions):
        self.states = states
        self._alphabet = alphabet
        self._initial = initial
        self._final = final

        self._nfsa = False

        self._current = initial
        self.matrix = {}
        for state in states:
            self.matrix[state] = {}

        for transition in transitions:
            s1, a, s2 = transition
            if s1 not in states:
                raise ValueError(Errors.E1.format(s1))
            if s2 not in states:
                raise ValueError(Errors.E1.format(s2))
            if a not in alphabet:
                raise ValueError(Errors.E3.format(a))

            if a in self.matrix[s1]:
                self._nfsa = True

            self.matrix[s1][a] = s2

        if not initial:
            raise ValueError(Errors.E4)

        if self._has_disjoint_states():
            raise ValueError(Errors.E2)

        for state in final:
            if state not in states:
                raise ValueError(Errors.E1.format(state))

        if initial not in states:
            raise ValueError(Errors.E1.format(initial))

        if self._nfsa:
            raise ValueError(Errors.E6)

    def _has_disjoint_states(self):
        graph = defaultdict(list)
        for s1 in self.states:
            for s2 in self.matrix[s1].values():
                graph[s1].append(s2)
                graph[s2].append(s1)

        visited = set()
        def dfs(state):
            visited.add(state)
            for next_state in graph[state]:
                if next_state not in visited:
                    dfs(next_state)

        dfs(self._initial)

        return len(visited) != len(self.states)

    def _every_state_reachable(self):
        visited = set()
        def dfs(state):
            visited.add(state)
            for next_state in self.matrix[state].values():
                if next_state not in visited:
                    dfs(next_state)

        dfs(self._initial)

        return len(visited) == len(self.states)

    def validate(self):
        warnings = []

        if self._nfsa:
            warnings.append(Errors.E6)

        return warnings

    def is_complete(self):
        for state in self.states:
            if len(self.matrix[state].values()) != len(self._alphabet):
                return False
        return True

    def as_regex(self):
        return FSARegexTranslator(self).translate()


def validate_lines(lines):
    import re
    match_1 = re.fullmatch(r'states={([a-zA-Z0-9]*?,)*([a-zA-Z0-9]*?)}', lines[0].strip())
    match_2 = re.fullmatch(r'alpha={([a-zA-Z0-9_]*?,)*([a-zA-Z0-9_]*?)}', lines[1].strip())
    match_3 = re.fullmatch(r'init\.st={[a-zA-Z0-9]*?}', lines[2].strip())
    match_4 = re.fullmatch(r'fin\.st={([a-zA-Z0-9]*?,)*([a-zA-Z0-9]*?)}', lines[3].strip())
    match_5 = re.fullmatch(r'trans={([a-zA-Z0-9]*?>[a-zA-Z0-9_]*?>[a-zA-Z0-9]*?,)*([a-zA-Z0-9]*?>[a-zA-Z0-9_]*?>[a-zA-Z0-9]*?)}', lines[4].strip())
    return match_1 and match_2 and match_3 and match_4 and match_5


def main():
    with open('fsa.txt', 'r') as f:
        lines = f.readlines()

        states = [state.strip() for state in lines[0].strip()[8:-1].split(',')]
        alphabet = [symbol.strip() for symbol in lines[1].strip()[7:-1].split(',')]
        initial = lines[2].strip()[9:-1]
        final = [state.strip() for state in lines[3].strip()[8:-1].split(',') if state]
        transitions = [
            [term.strip() for term in transition.split('>')] for transition in lines[4].strip()[7:-1].split(',')
        ]

    out_lines = []

    if not validate_lines(lines):
        out_lines.append('Error:')
        out_lines.append('E5: Input is malformed')
        with open('result.txt', 'w') as f:
            f.write('\n'.join(out_lines))
        return

    try:
        fsa = FSA(states, alphabet, initial, final, transitions)
    except ValueError as e:
        out_lines.append('Error:')
        out_lines.append(str(e))
        with open('result.txt', 'w') as f:
            f.write('\n'.join(out_lines))
        return

    out_lines.append(fsa.as_regex())

    with open('result.txt', 'w') as f:
        f.write('\n'.join(out_lines))


if __name__ == '__main__':
    main()