import java.io.*;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class FSM {
    public static void main(String[] args) {
        if(args.length == 2) {
            HashMap<String, State> fsm = interpret(args[0]);
            validate(fsm, args[0], args[1]);
        }
    }

    public static HashMap<String, State> interpret(String machine) {
        try {
            Scanner in = new Scanner(new File(machine));
            //BufferedReader m = new BufferedReader(new InputStreamReader(new FileInputStream(machine)));
            //<state>, <next_state>, <transition_symbols>
            HashMap<String, State> fsm = new HashMap<String, State>();

            String transition_symbols = "";
            boolean transition_sentinal = false;

            State state = new State("", "", new ArrayList<State>(), new ArrayList<Character>());
            State next_state = new State("", "", new ArrayList<State>(), new ArrayList<Character>());
            while(in.hasNextLine()) {
                String[] tokens = in.nextLine().split(" ");
                for(int i=0; i < tokens.length; i++)  {
                    String token = tokens[i];
                    //Process current state
                    if(i==0) {
                        String state_name = "";
                        for(int j=0; j < token.length(); j++) {
                            Matcher match_alpha = Pattern.compile("[a-z0-9]").matcher(token.charAt(j)+"");
                            Matcher match_state_mod = Pattern.compile("[!@$]").matcher(token.charAt(j)+"");
                            if(match_alpha.find()) {
                                state_name += token.charAt(j);
                            } else if(match_state_mod.find()) {
                                state.addStateMod(token.charAt(j));
                            }
                        }
                        state.setStateName(state_name);

                        fsm.put(state_name, state);
                    } else {
                        // Process Transitions
                        String state_name = "";
                        for(int j=0; j < token.length(); j++) {
                            Matcher match_alpha = Pattern.compile("[a-z0-9]").matcher(token.charAt(j)+"");
                            if(token.charAt(j) == ':') {
                                next_state.setStateName(state_name);
                                for(int k=0; k < state.getTransitions().size(); k++) {
                                    next_state.addTransition(state.getTransitions().get(k));
                                }
                                for(int k=0; k < state.getStateMod().size(); k++) {
                                    next_state.addStateMod(state.getStateMod().get(k));
                                }
                                fsm.put(state_name, next_state);
                                //if(fsm.containsKey(state_name)) {
                                    next_state.addTransition(next_state);
                                //}
                                state.addTransition(next_state);

                                transition_sentinal = true;
                            } else if(match_alpha.find() && !transition_sentinal) {
                                state_name += token.charAt(j);
                            } else if(transition_sentinal) {
                                if(token.charAt(j) == '|') {
                                    String shortCut = token.charAt(j)+"";
                                    j++;
                                    shortCut += token.charAt(j);
                                    transition_symbols += getShortCuts(shortCut);
                                    transition_symbols += next_state.getTransitionSymbols();

                                    next_state.setTransitionSymbols(transition_symbols);

                                    transition_symbols = "";
                                } else {
                                    transition_symbols += token.charAt(j);
                                    transition_symbols += next_state.getTransitionSymbols();

                                    next_state.setTransitionSymbols(transition_symbols);

                                    transition_symbols = "";
                                }
                            }
                        }
                        next_state = new State("", "", new ArrayList<State>(), new ArrayList<Character>());
                        transition_sentinal = false;
                    }
                }
                state = new State("", "", new ArrayList<State>(), new ArrayList<Character>());
            }

            return fsm;

        } catch(Exception e) {
            System.out.println(e);
            return null;
        }
    }

    public static void validate(HashMap<String, State> fsm, String machine, String input) {
        try {
            BufferedReader m = new BufferedReader(new InputStreamReader(new FileInputStream(input)));
            int r;
            State s = getStateWithMod(fsm, '@');
            String line = "";
            while((r = m.read()) != -1 && s != null) {
                char in = (char) r;
                if(in != '\n') {
                    // Go to next state depending on what in is
                    line += in;
                    s = getTransitionStateFrom(s, in);
                    //System.out.println();
                } else {
                    if(s.getStateMod().contains('$')) {
                        System.out.println(machine+" Accepted: "+line);
                    } else {
                        System.out.println(machine+" Rejected: "+line);
                    }
                    s = getStateWithMod(fsm, '@');
                    line = "";
                }
            }
        } catch(Exception e) {

        }
    }

    public static State getStateWithMod(HashMap<String, State> fsm, char mod) {
        Iterator<State> it = fsm.values().iterator();
        while(it.hasNext()) {
            State s = it.next();
            if(s.getStateMod().contains(mod)) {
                return s;
            }
        }
        return null;
    }

    public static State getTransitionStateFrom(State s, char in) {
        State next_state;
        for(int i=0; i < s.getTransitions().size(); i++) {
            next_state = s.getTransitions().get(i);
            if(next_state.getTransitionSymbols().contains(in+"")) {
                return next_state;
            }
        }
        return null;
    }

    public static String getShortCuts(String s) {
        if(s.equals("|d")) {
            return "0123456789";
        } else if(s.equals("|n")) {
            return "123456789";
        } else if(s.equals("|a")) {
            return "abcdefghijklmnopqrstuvwxyz";
        } else if(s.equals("|s")) {
            return "!@#%/&*-+(){}.,";
        } else {
            return "";
        }
    }

    static class State {
        private String state_name;
        private String transition_symbols;
        private ArrayList<Character> state_modifiers;
        private ArrayList<State> transitions;

        public State(String state, String ts, ArrayList<State> t, ArrayList<Character> state_mod) {
            this.state_name = state;
            this.transition_symbols = ts;
            this.state_modifiers = state_mod;
            this.transitions = t;
        }

        public String getStateName() {
            return this.state_name;
        }

        public ArrayList<Character> getStateMod() {
            return this.state_modifiers;
        }

        public ArrayList<State> getTransitions() {
            return this.transitions;
        }

        public void addTransition(State s) {
            this.transitions.add(s);
        }

        public String getTransitionSymbols() {
            return this.transition_symbols;
        }

        public void setTransitions(ArrayList<State> t) {
            this.transitions = t;
        }

        public void setTransitionSymbols(String t) {
            this.transition_symbols = t;
        }

        public void setStateName(String state) {
            this.state_name = state;
        }

        public void setStateMod(ArrayList<Character> state_mod) {
            this.state_modifiers = state_mod;
        }

        public void addStateMod(char ch) {
            this.state_modifiers.add(ch);
        }
    }
}