import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws FileNotFoundException {
        Scanner scanner = new Scanner(new File("fsa.txt"));
        PrintWriter result = new PrintWriter("result.txt");

        Validator fsaValid = new Validator(scanner, result);
        fsaValid.start();

        RegexBuilder regexBuilder = new RegexBuilder(fsaValid.getStates(), fsaValid.getInitState(),
                fsaValid.getFinStates());
        String regex = regexBuilder.build();

        result.print(regex);

        scanner.close();
        result.close();
    }
}

class State {
    State(String name) {
        this.name = name;
        this.transition = new LinkedList<>();
    }

    private String name;
    private LinkedList<Transition> transition;

    public String getName() {
        return name;
    }

    public void addTrans(String letter, State state) {
        transition.add(new Transition(letter, state));
    }

    public LinkedList<Transition> getTrans() {
        return transition;
    }
}

class Validator {
    private PrintWriter result;
    private LinkedList<State> states; // states of FSA
    private LinkedList<String> alpha; // alphabet of FSA
    private State initState; // initial state of FSA
    private LinkedList<State> finState; // final state of FSA
    private LinkedList<Transition> transitions; // transitions of FSA

    Validator(Scanner scanner, PrintWriter result) {
        this.result = result;

        HashMap fileData = formatInFile(scanner);

        this.states = (LinkedList<State>) fileData.get("states");
        this.alpha = (LinkedList<String>) fileData.get("alpha");
        this.initState = (State) fileData.get("initState");
        this.finState = (LinkedList<State>) fileData.get("finState");
        this.transitions = (LinkedList<Transition>) fileData.get("trans");
    }

    private HashMap formatInFile(Scanner scanner) {
        HashMap fileData = new HashMap<>();

        String statesString = scanner.nextLine(); // input strings
        String alphaString = scanner.nextLine();
        String initStateString = scanner.nextLine();
        String finStateString = scanner.nextLine();
        String transString = scanner.nextLine();

        if (fileIsMalformed(statesString, alphaString, initStateString, finStateString, transString)) {
            result.print("Error:\nE5: Input file is malformed"); // E5 check
            result.close();
            System.exit(0);
        }

        LinkedList<State> states = formatStates(statesString); // reformat lines
        LinkedList<String> alpha = formatAlpha(alphaString);
        State initState = formatInitState(initStateString, states);
        LinkedList<State> finStates = formatFinStates(finStateString, states);
        LinkedList<Transition> trans = formatTrans(transString, states, alpha);

        fileData.put("states", states);
        fileData.put("alpha", alpha);
        fileData.put("initState", initState);
        fileData.put("finState", finStates);
        fileData.put("trans", trans);

        return fileData;
    }

    private boolean fileIsMalformed(String statesString, String alphaString, String initStateString,
            String finStateString, String transString) {
        if ((!(statesString.contains("[") && statesString.contains("]")) || !statesString.contains("=")
                || statesString.contains(" "))
                || (!(alphaString.contains("[") && alphaString.contains("]")) || !alphaString.contains("=")
                        || alphaString.contains(" "))
                || (!(initStateString.contains("[") && initStateString.contains("]")) || !initStateString.contains("=")
                        || initStateString.contains(" "))
                || (!(finStateString.contains("[") && finStateString.contains("]")) || !finStateString.contains("=")
                        || finStateString.contains(" "))
                || (!(transString.contains("[") && transString.contains("]")) || !transString.contains("=")
                        || transString.contains(" ")))
            return true;

        if (!(statesString.substring(0, 8).equals("states=[") & statesString.charAt(statesString.length() - 1) == ']'
                & alphaString.substring(0, 7).equals("alpha=[") & alphaString.charAt(alphaString.length() - 1) == ']'
                & initStateString.substring(0, 9).equals("init.st=[")
                & initStateString.charAt(initStateString.length() - 1) == ']'
                & finStateString.substring(0, 8).equals("fin.st=[")
                & finStateString.charAt(finStateString.length() - 1) == ']'
                & transString.substring(0, 7).equals("trans=[") & transString.charAt(transString.length() - 1) == ']'))
            return true;

        return false;
    }

    private LinkedList<State> formatStates(String statesStr) {
        LinkedList<State> resStates = new LinkedList<>();
        String[] states = statesStr.substring(8, statesStr.length() - 1).split(",");

        for (String stateName : states)
            resStates.add(new State(stateName));

        return resStates;
    }

    // convert string according alphabet
    private LinkedList<String> formatAlpha(String alphaStr) {
        LinkedList<String> resAlpha = new LinkedList<>();
        String[] alpha = alphaStr.substring(7, alphaStr.length() - 1).split(",");

        resAlpha.addAll(Arrays.asList(alpha));

        return resAlpha;
    }

    // convert string according initial states
    private State formatInitState(String initStateStr, LinkedList<State> states) {
        String initStateName = initStateStr.substring(9, initStateStr.length() - 1);

        return findByName(initStateName, states);
    }

    // convert string according final states
    private LinkedList<State> formatFinStates(String finStateStr, LinkedList<State> states) {
        LinkedList<State> resFinStates = new LinkedList<>();
        String[] finStates = finStateStr.substring(8, finStateStr.length() - 1).split(",");

        for (String finState : finStates)
            if (!finState.equals(""))
                resFinStates.add(findByName(finState, states));

        return resFinStates;
    }

    // convert string according alphabet transitions
    private LinkedList<Transition> formatTrans(String transStr, LinkedList<State> states, LinkedList<String> alpha) {
        LinkedList<Transition> resTrans = new LinkedList<>();
        String[] trans = transStr.substring(7, transStr.length() - 1).split(",");

        for (String transitionStr : trans) {
            String[] transSep = transitionStr.split(">");
            State state1 = findByName(transSep[0], states);
            State state2 = findByName(transSep[2], states);

            if (!alpha.contains(transSep[1])) { // E3 check
                result.print("Error:\nE3: A transition '" + transSep[1] + "' is not represented in the alphabet");
                result.close();
                System.exit(0);
            }

            if (state1 != null & state2 != null)
                state1.addTrans(transSep[1], state2);

            resTrans.add(new Transition(transSep[1], state1, state2));
        }

        return resTrans;
    }

    // find state according the name
    private State findByName(String name, LinkedList<State> states) {
        for (State state : states)
            if (state.getName().equals(name))
                return state;

        if (!name.equals("")) { // E1 check
            result.print("Error:\nE1: A state '" + name + "' is not in set of states");
            result.close();
            System.exit(0);
        }
        return null;
    }

    public void start() {
        if (initState == null) { // E4 check
            result.print("Error:\nE4: Initial state is not defined");
            result.close();
            System.exit(0);
        }

        LinkedList<State> undirectedStates = makeUndirected(deepClone(states));
        LinkedList<State> reachedStates = getReachableStatesFrom(undirectedStates.get(0), new LinkedList<>());

        if (reachedStates.size() != states.size()) { // check E2
            result.print("Error:\nE2: Some states are disjoint");
            result.close();
            System.exit(0);
        }

        if (fsaIsNondeterministic()) { // check E6
            result.print("Error:\nE6: FSA is nondeterministic");
            result.close();
            System.exit(0);
        }

        if (finState.size() == 0) {
            result.print("{}");
            result.close();
            System.exit(0);
        }
    }

    private LinkedList<State> deepClone(LinkedList<State> states) {
        LinkedList<State> newStates = new LinkedList<>();

        for (State state : states)
            newStates.add(new State(state.getName()));

        for (int i = 0; i < states.size(); i++)
            for (Transition trans : states.get(i).getTrans()) {
                State state = findByName(trans.getTarget().getName(), newStates);
                newStates.get(i).addTrans(trans.getLetter(), state);
            }

        return newStates;
    }

    private LinkedList<State> makeUndirected(LinkedList<State> states) {
        for (State state : states)
            for (Transition trans : state.getTrans())
                if (state != trans.getTarget()
                        & !trans.getTarget().getTrans().contains(new Transition(trans.getLetter(), state)))
                    trans.getTarget().addTrans(trans.getLetter(), state);
        return states;
    }

    private LinkedList<State> getReachableStatesFrom(State state, LinkedList<State> result) {
        result.add(state);
        for (Transition trans : state.getTrans())
            if (!result.contains(trans.getTarget()))
                result = getReachableStatesFrom(trans.getTarget(), result);
        return result;
    }

    private boolean fsaIsNondeterministic() {
        LinkedList<String> localTrans = new LinkedList<>();

        for (Transition trn : transitions) {
            if (localTrans.contains(trn.getLetter() + ">" + trn.getSource().getName()))
                return true;
            localTrans.add(trn.getLetter() + ">" + trn.getSource().getName());
        }

        return false;
    }

    public LinkedList<State> getStates() {
        return states;
    }

    public State getInitState() {
        return initState;
    }

    public LinkedList<State> getFinStates() {
        return finState;
    }
}

class RegexBuilder {
    private LinkedList<State> states; // states of FSA
    private State initState; // initial state of FSA
    private LinkedList<State> finStates; // final state of FSA
    private int initIndex; // index of initial state in states list
    private LinkedList<Integer> finIndexes; // indexes of final states in states list

    RegexBuilder(LinkedList<State> states, State initState, LinkedList<State> finStates) {
        this.states = states;
        this.initState = initState;
        this.finStates = finStates;

        this.initIndex = 0;
        this.finIndexes = new LinkedList<>();
    }

    public String build() {
        String[][] R = getInitRegex();

        for (int i = 0; i < states.size(); i++) {
            String[][] newR = new String[states.size()][states.size()];

            for (int j = 0; j < states.size(); j++)
                for (int k = 0; k < states.size(); k++)
                    newR[j][k] = "(" + R[j][i] + ")(" + R[i][i] + ")*(" + R[i][k] + ")|(" + R[j][k] + ")";

            R = newR;
        }

        String result = "";
        for (int j : finIndexes)
            result = result.concat(R[initIndex][j]) + "|";

        return result.substring(0, result.length() - 1);
    }

    private String[][] getInitRegex() {
        String[][] initRegex = new String[states.size()][states.size()];

        for (int j = 0; j < states.size(); j++)
            if (finStates.contains(states.get(j)))
                finIndexes.add(j);

        for (int i = 0; i < states.size(); i++) {
            State state1 = states.get(i);

            if (state1 == initState)
                initIndex = i;

            for (int j = 0; j < states.size(); j++) {
                State state2 = states.get(j);
                String reg = "";

                for (Transition trans : state1.getTrans())
                    if (trans.getTarget() == state2)
                        reg = reg.concat(trans.getLetter() + "|");

                if (state1 == state2)
                    reg = reg.concat("eps");
                if (reg.isEmpty())
                    reg = "{}";
                if (reg.charAt(reg.length() - 1) == '|')
                    reg = reg.substring(0, reg.length() - 1);

                initRegex[i][j] = reg;
            }
        }

        return initRegex;
    }
}

class Transition {
    Transition(String letter, State source, State target) {
        this.letter = letter;
        this.source = source;
        this.target = target;
    }

    Transition(String letter, State target) {
        this.letter = letter;
        this.source = null;
        this.target = target;
    }

    private String letter;
    private State source;
    private State target;

    public String getLetter() {
        return letter;
    }

    public State getSource() {
        return source;
    }

    public State getTarget() {
        return target;
    }
}