В файле filename + ".in" в первой строке — число тестов, со следующей строки — тесты в формате <вход>\n<ответ>. После этого нужно добавить строки accept: AC reject: RJ blank: _ start: S В конце — описание машины Тьюринга. Функцию check, если хочется, можно написать.

gistfile1.java

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

public class InterpretatorMulti {
	int tapesCount;
	String blank;
	State accept;
	State reject;
	State start;
	Map<String, State> states;

	private void solve() throws IOException {
		int n = in.nextInt();
		ArrayList<String> input = new ArrayList<String>();
		ArrayList<String> output = new ArrayList<String>();
		for (int i = 0; i < n; ++i) {
			String tapeStr = br.readLine();
			input.add(tapeStr);
			String answer = br.readLine();
			output.add(answer);
		}
		initTuringMachine();
		for (int i = 0; i < n; ++i) {
			out.println("Test #" + i);
			runTest(i, input.get(i), output.get(i));
		}
	}

	private void runTest(int testNumber, String tapeStr, String answer)
			throws IOException {
		Tape[] tapes = new Tape[tapesCount];
		tapes[0] = new Tape(tapeStr, blank);
		for (int i = 1; i < tapesCount; ++i) {
			tapes[i] = new Tape("", blank);
		}
		final int maxSteps = 10000000;
		int step = 0;
		State curr = start;
		while (tapes[0].peek().equals(blank)) {
			tapes[0].move(Direction.right);
		}
		while (step < maxSteps && !curr.equals(accept)) {
			out.println(Arrays.toString(tapes) + " | " + curr.toString());
			++step;
			List<String> tapeChars = new ArrayList<String>();
			for (int i = 0; i < tapesCount; ++i) {
				tapeChars.add(tapes[i].peek());
			}
			if (!curr.go.containsKey(tapeChars)) {
				curr = reject;
				break;
			}
			CharsDirectionsState r = curr.go.get(tapeChars);
			for (int i = 0; i < tapesCount; ++i) {
				tapes[i].write(r.replacements[i]);
				tapes[i].move(r.dirs[i]);
			}
			curr = r.to;
		}
		if (step == maxSteps) {
			System.err.println("Test #" + testNumber + " : TL");
			return;
		}
		out.println(Arrays.toString(tapes) + " | " + curr.toString());
		out.println(answer);
		if (check(tapes, answer)) {
			System.err.println("Test #" + testNumber + " : OK");
		} else {
			System.err.println("Test #" + testNumber + " : FAIL");
			System.err.println("Answer : " + answer);
			System.err.println(curr);
			System.err.println("Output : " + tapes[0].toString());
		}
	}

	private boolean check(Tape[] tapes, String answer) {
		// TODO Auto-generated method stub
		return false;
	}

	private void exit(String message) {
		System.err.println(message);
		System.exit(1);
	}

	private void initTuringMachine() throws IOException {
		states = new HashMap<String, State>();
		initMainStatesBlankTapesCount();
		while (br.ready()) {
			addRule(br.readLine());
		}
	}

	private void addRule(String rule) {
		System.err.println(rule);
		final String errorMessage = "Wrong format : " + rule;
		StringTokenizer st = new StringTokenizer(rule);
		String fromStateName = st.nextToken();
		List<String> tapesChar = new ArrayList<String>();
		for (int i = 0; i < tapesCount; ++i) {
			tapesChar.add(st.nextToken());
		}
		String tmp = st.nextToken();
		if (!tmp.equals("->")) {
			exit(errorMessage);
		}
		String toStateName = st.nextToken();
		String[] newTapeChars = new String[tapesCount];
		Direction[] directions = new Direction[tapesCount];
		for (int i = 0; i < tapesCount; ++i) {
			newTapeChars[i] = st.nextToken();
			char dir = st.nextToken().charAt(0);
			directions[i] = directionFromChar(dir);
		}
		assert !st.hasMoreTokens() : errorMessage;
		if (!states.containsKey(fromStateName)) {
			states.put(fromStateName, new State(fromStateName));
		}
		if (!states.containsKey(toStateName)) {
			states.put(toStateName, new State(toStateName));
		}
		State from = states.get(fromStateName);
		State to = states.get(toStateName);
		if (from.go.containsKey(tapesChar)) {
			exit("Dublication : " + from.toString() + " | " + rule);
		}
		from.go.put(tapesChar, new CharsDirectionsState(to, newTapeChars,
				directions));
	}

	private void initMainStatesBlankTapesCount() {
		for (int i = 0; i < 4; ++i) {
			String what = in.next();
			String value = in.next();
			switch (what.charAt(0)) {
			case 'a':
				accept = new State(value);
				states.put(value, accept);
				break;
			case 'r':
				reject = new State(value);
				states.put(value, reject);
				break;
			case 'b':
				blank = value;
				break;
			case 's':
				start = new State(value);
				states.put(value, start);
				break;
			default:
				exit("wut? " + what + ' ' + value);
				break;
			}
		}
		if (blank == null) {
			exit("no blank");
		}
		if (accept == null) {
			exit("no accept");
		}
		if (reject == null) {
			exit("no reject");
		}
		if (start == null) {
			exit("no start");
		}
		tapesCount = in.nextInt();
	}

	enum Direction {
		left, right, stay
	};

	Direction directionFromChar(char dir) {
		switch (dir) {
		case '>':
			return Direction.right;
		case '<':
			return Direction.left;
		case 'V':
		case '^':
			return Direction.stay;
		default:
			exit("directionFromChar : Wrong dir : " + dir);
		}
		return null;
	}

	class Tape {
		Stack<String> left, right;

		Tape(String value, String blank) {
			StringTokenizer st = new StringTokenizer(new StringBuilder(value)
					.reverse().toString());
			left = new Stack<String>();
			right = new Stack<String>();
			while (st.hasMoreTokens()) {
				right.push(st.nextToken());
			}
		}

		@SuppressWarnings("unchecked")
		public String toString() {
			StringBuilder sb = new StringBuilder();
			appendLeft(sb);
			Stack<String> rr = (Stack<String>) right.clone();
			appendHeadChar(sb, rr);
			rightAppend(sb, rr);
			return sb.toString();
		}

		private void appendHeadChar(StringBuilder sb, Stack<String> rr) {
			sb.append('[');
			if (!rr.empty()) {
				sb.append(rr.pop());
			} else {
				sb.append(blank);
			}
			sb.append("] ");
		}

		private void rightAppend(StringBuilder sb, Stack<String> rr) {
			if (sb.length() > 0) {
				sb.append(' ');
			}
			while (!rr.empty()) {
				sb.append(rr.pop());
				sb.append(' ');
			}
		}

		@SuppressWarnings("unchecked")
		private void appendLeft(StringBuilder sb) {
			Stack<String> ll = (Stack<String>) left.clone();
			while (!ll.empty()) {
				sb.append(' ');
				sb.append(ll.pop());
			}
			sb.reverse();
		}

		@SuppressWarnings("unchecked")
		public String tape() {
			StringBuilder sb = new StringBuilder();
			appendLeftWithoutBlank(sb);
			Stack<String> rr = (Stack<String>) right.clone();

			rightAppend(sb, rr);
			return sb.toString();
		}

		@SuppressWarnings("unchecked")
		private void appendLeftWithoutBlank(StringBuilder sb) {
			Stack<String> ll = (Stack<String>) left.clone();
			Stack<String> llrev = new Stack<String>();
			while (!ll.empty()) {
				llrev.push(ll.pop());
			}
			while (!llrev.empty() && llrev.peek().equals(blank)) {
				llrev.pop();
			}
			while (!llrev.empty()) {
				sb.append(' ');
				sb.append(llrev.pop());
			}
		}

		String peek() {
			if (right.empty()) {
				right.push(blank);
			}
			return right.peek();
		}

		void write(String value) {
			if (!right.empty()) {
				right.pop();
			}
			right.push(value);
		}

		void move(Direction dir) {
			switch (dir) {
			case left:
				if (left.empty()) {
					left.push(blank);
				}
				right.push(left.pop());
				break;
			case right:
				if (right.empty()) {
					right.push(blank);
				}
				left.push(right.pop());
				break;
			case stay:
				break;
			}
		}
	}

	class CharsDirectionsState {
		String[] replacements;
		State to;
		Direction[] dirs;

		public CharsDirectionsState(State to, String[] replacements,
				Direction[] dirs) {
			this.to = to;
			this.replacements = replacements;
			this.dirs = dirs;
		}

	}

	class State {
		String name;

		public String toString() {
			return name;
		}

		Map<List<String>, CharsDirectionsState> go = new HashMap<List<String>, CharsDirectionsState>();

		public State(String name) {
			this.name = name;
		}

	}

	public void run() {
		Locale.setDefault(Locale.US);
		in = new MyScanner();
		try {
			out = new PrintWriter(new FileWriter(filename + ".out"));
			solve();
		} catch (IOException e) {
			e.printStackTrace();
		}

		in.close();
		out.close();
	}

	public static void main(String[] args) {
		new InterpretatorMulti().run();
	}

	private BufferedReader br;
	private StringTokenizer st;
	private MyScanner in;
	private PrintWriter out;

	private final String filename = "filename";

	private class MyScanner {
		public MyScanner() {
			try {
				br = new BufferedReader(new FileReader(filename + ".in"));
			} catch (FileNotFoundException e) {
				e.printStackTrace();
			}
		}

		public String next() {
			try {
				while (st == null || !st.hasMoreTokens()) {
					st = new StringTokenizer(br.readLine());
				}
				return st.nextToken();
			} catch (IOException e) {
				e.printStackTrace();
				return null;
			}
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public void close() {
			try {
				br.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
	}
}