import java.util.Scanner;
import java.io.PrintStream;
import java.util.Vector;
import java.lang.String;
import java.util.HashMap;
import java.util.regex.Pattern;

// To compile, type "javac TM.java"
// Type your Turing machine description into a file, say a6.txt
// To test your Turing machine, type "java -ea TM < a6.txt"
// If your file format is incorrect, it should throw an exception.
// The programme below will print a description of your Turing machine
// (just so you can doublecheck that it doesn't contain any errors) and then
// will test it on all short strings.

// It's not the most beautifully written code, but it should do the job.

// If you want to see the details of the execution of your machine on
// each input string, change "false" to "true" in the line that
// calls machine.run(...)

public class A6 {
    final int numStates; // number of states in the state set
    final int tapeAlphaSize; // number of characters in the tape alphabet
    final int inputAlphaSize; // number of characters in the input alphabet
    final HashMap<String,Integer> alphabet;
    final String[] alphabetArray;

    int[][] nextState; // these three arrays are used to store the transition function
    int[][] charToWrite;
    boolean[][] moveLeft;

    float scorePos; // variables to keep track of scores
    float scoreNeg;
    float numPos;
    float numNeg;
    boolean fail;
    float infloop;

    static final String blank = "blank";
    static final String leftend = "leftend";

    public A6(Scanner in) {
	// Creates a Turing machine by reading it (in YUTMFF) from in.

	scorePos = 0;
	scoreNeg = 0;
	numPos = 0;
	numNeg = 0;
	fail = false;
	infloop = 0;

	numStates = in.nextInt();
	assert numStates >= 3;
	tapeAlphaSize = in.nextInt();
	inputAlphaSize = in.nextInt();
	assert inputAlphaSize >= 1 && tapeAlphaSize >= inputAlphaSize + 2;
	alphabet = new HashMap<String,Integer>(tapeAlphaSize);
	alphabetArray = new String[tapeAlphaSize];

	for (int i = 0; i < tapeAlphaSize - 2; i++) {
	    String s = in.next();
	    assert !alphabet.containsKey(s) && !s.equals(blank) && ! s.equals(leftend);
	    alphabet.put(s,i);
	    alphabetArray[i]=s;
	}
	alphabetArray[tapeAlphaSize-2] = blank;
	alphabetArray[tapeAlphaSize-1] = leftend;
	alphabet.put(blank,tapeAlphaSize-2);
	alphabet.put(leftend,tapeAlphaSize-1);

	nextState =    new int[numStates-2][tapeAlphaSize];
	charToWrite =  new int[numStates-2][tapeAlphaSize];
	moveLeft = new boolean[numStates-2][tapeAlphaSize];

	boolean[][] done = new boolean[numStates-2][tapeAlphaSize]; 
	// temporary variable used to make sure that each transition is 
	// only defined once in the input

	for (int i = 0; i < numStates-2; i++) {
	    for (int j = 0; j < tapeAlphaSize; j++) {
		// set default values
		nextState[i][j] = i;
		charToWrite[i][j] = j;
		moveLeft[i][j] = false;
		done[i][j] = false;
	    }
	}
	
	// Read in transitions
	int numTransitions = in.nextInt();
	for (int k = 0; k < numTransitions; k++) {
	    int i = in.nextInt();
	    assert i >= 0 && i < numStates - 2;
	    String s = in.next();
	    assert alphabet.containsKey(s);
	    int j = alphabet.get(s);
	    assert !done[i][j];
	    done[i][j] = true;

	    nextState [i][j] = in.nextInt();
	    assert nextState[i][j] >= 0 && nextState[i][j] < numStates;
	    String character = in.next();
	    assert alphabet.containsKey(character);
	    charToWrite[i][j] = alphabet.get(character);
	    String direction = in.next();
	    assert direction.equals("L") || direction.equals("R");
	    moveLeft[i][j] = (direction.equals("L"));

	    if (j == leftEnd()) {
		// check that left-end marker is handled correctly
		assert !moveLeft[i][j] && charToWrite[i][j] == leftEnd();
	    }
	}
    }

    private final int blank() { return tapeAlphaSize - 2; }
    final int leftEnd() { return tapeAlphaSize - 1; } 
    private final int acceptState() { return numStates - 2; }
    private final int rejectState() { return numStates - 1; }

    void print(PrintStream out) {
	out.print("Tape alphabet:");
	for (int i = 0; i < tapeAlphaSize; i++)
	    out.print(" " + alphabetArray[i]);
	out.println("");
	out.println("Input alphabet size = " + inputAlphaSize);
	out.println("Transition table:");
	for (int i = 0; i < numStates - 2; i++)
	    for (int j = 0; j < tapeAlphaSize; j++) 
		out.println("delta(" + i + "," + alphabetArray[j]  
			    + ") = (" + nextState[i][j] + ","
			    + alphabetArray[charToWrite[i][j]] + ","  
			    + (moveLeft[i][j] ? "L)" : "R)"));
    }

    private void printConfig(PrintStream out, int stepCounter, Vector<Integer> tape, 
			     int state, int pos) {
	// Prints a configuration of the machine.

	out.print("Configuration after " + stepCounter + " steps: ");
	for (int i = 0; i < tape.size(); i++) {
	    if (pos==i) out.print("q" + state + " ");
	    out.print(alphabetArray[tape.get(i)] + " ");
	}
	if (pos==tape.size()) out.print("q" + state + " ");
	out.println();
    }

    public String vector2string(Vector<Integer> s) { 
	String res = "";
	for (int i=0; i < s.size(); i++) {
	    res = res + alphabetArray[s.elementAt(i)];
	}
	return res;
    }

    public void printString(PrintStream out, Vector<Integer> s) {
        if (s.size() == 0)
            out.print("The empty string");
        else {
            out.print("\"" + alphabetArray[s.firstElement()]);
            for (int i = 1; i < s.size(); i++)
                out.print(" " + alphabetArray[s.elementAt(i)]);
            out.print("\"");
        }
    }

    public void run(Scanner in, PrintStream out, int numSteps, boolean trace) {
	// Reads a string from in and runs the Turing machine on it.
	// Format for input string:  sequence of integers separated by spaces
	// giving each character, terminated by -1.
    
	int state=0; // start in state 0
	int pos = 1; // head position
	Vector<Integer> tape = new Vector<Integer>(10000,0); // tape contents

	// Initialize tape with input string
	tape.add(leftEnd());
	String nextChar = in.next();
	while (nextChar != blank) {	
	    assert alphabet.containsKey(nextChar);
	    tape.add(alphabet.get(nextChar));
	    nextChar = in.next();
	}

	run(tape, out, numSteps, trace);
    }
 
    int run(Vector<Integer> tape, PrintStream out, int numSteps, boolean trace) {
	// Runs the Turing machine on input tape
    
	int state = 0; // start in state 0
	int pos = 1; // head position

	if (trace) out.println("NEXT INPUT STRING");

	// Run the machine for numSteps steps
	int stepCounter = 0;
	if (trace) printConfig(out, stepCounter, tape, state, pos);
	while (state < acceptState() && stepCounter++ <= numSteps) { 
	    // simulate one step of the Turing machine
	    if (pos == tape.size()) // extend tape if TM has run beyond right end
		tape.add(blank());
	    int oldChar = tape.get(pos);
	    tape.set(pos, charToWrite[state][oldChar]);
	    pos = (moveLeft[state][oldChar]) ? pos - 1 : pos + 1;
	    state = nextState[state][oldChar];
	    if (trace) printConfig(out, stepCounter, tape, state, pos);
	}
	if (state == acceptState()) {
	    if (trace) out.println("Turing machine has accepted after " + stepCounter + " steps.");
	    return 1; }
	else if (state == rejectState()) {
	    if (trace) out.println("Turing machine has rejected after " + stepCounter + " steps.");
	    return 0; }
	else {
	    if (trace) out.println("Turing machine ran for " + stepCounter + " steps without halting.");
	    return -1; }
    }

    public void test(Vector<Integer> testString, PrintStream out) {
	int maxsteps = 10000;

	Vector<Integer> tape = new Vector<Integer>(100,0);
	tape.add(leftEnd());
	for (int i = 0; i < testString.size(); i++) {
	    tape.add(testString.elementAt(i));
	}
	int output = run(tape, out, maxsteps, false);

	// check against correct output
	String s = vector2string(testString);
	int numA = s.indexOf('b');
	int numB = s.indexOf('c') - s.indexOf('b');
	int numC = s.length() - s.indexOf('c');
	    
	if (Pattern.matches("a+b+c+", s)) {
	    if (numC != numA * numB) {
		numNeg++;
		if (output == 0) scoreNeg++;
	    } else if (numC == numA * numB) {
		numPos++;
		if (output == 1) scorePos++;
	    }
	}
	else if (output != 0)
	    fail = true;
	if (output == -1) infloop++;

	//printString(out, testString);
	//if (output == -1)
	//    out.println(":  on this input, the machine did not terminate within " 
	//	    + maxsteps + " steps");
	// else {
	//     out.println(output==1 ? " was accepted" : " was rejected");
	// }
    }

    public static void main(String[] args){
	Scanner in = new Scanner(System.in);
	PrintStream out = System.out;
	
	A6 machine = new A6(in);

	machine.print(out);

	out.println("Starting to test input strings");

        Vector<Integer> testString = new Vector<Integer>(0);

	int maxlength = 12;
	// test all strings of length <= maxlength

	while (testString.size() <= maxlength) {
	    machine.test(testString, out);
	    // increment test String
	    int pos = testString.size()-1;
	    while (pos >= 0 && testString.elementAt(pos) == machine.inputAlphaSize-1) {
		testString.set(pos,0);
		pos--;
	    }
	    if (pos >= 0)
		testString.set(pos, testString.elementAt(pos) + 1);
	    else
		testString.add(0);
	}

	// test some more strings that are in the language
	for (int i = 1; i < 9; i++)
	    for (int j = 1; j < 9; j++) {
		testString = new Vector<Integer>(0);
		for (int k = 0; k < i; k++)
		    testString.add(0);
		for (int k = 0; k < j; k++)
		    testString.add(1);
		for (int k = 0; k < i * j; k++)
		    testString.add(2);
		machine.test(testString, out);
	    }

	if (machine.infloop > 0) { 
	    out.print("Your machine did not terminate on ");
	    out.print(machine.infloop);
	    out.println(" of the strings tested.");
	}
	out.println(machine.fail ? 
		   "Your machine did not reject all strings that are not of the form a+b+c+." : 
		   "Your machine correctly rejected strings that are not of the form a+b+c+.");
	out.println("Of the strings of the form a+b+c+ that I tested:");
	out.print("Your machine correctly accepted ");
	out.print(machine.scorePos);
	out.print(" of the ");
	out.print(machine.numPos);
	out.println(" strings in the language.");
	out.print("Your machine correctly rejected ");
	out.print(machine.scoreNeg);
	out.print(" of the ");
	out.print(machine.numNeg);
	out.println(" strings not in the language.");
	out.print("Final grade is ");
	out.print((machine.fail ? 0 : 2) + Math.max(0,(machine.scorePos/machine.numPos + machine.scoreNeg/machine.numNeg - 1) * 8));
	out.println(" out of 10.");
    }	

}