有限オートマトンをプログラムで組んでみた

/**
 * 状態の集合
 */
private Set<String> statusSet;

/**
 * 入力記号の集合
 */
private Set<Character> sigmaSet;

/**
 * 状態遷移関数の定義
 */
private Map<String, Map<Character, String>> deltaMap;

/**
 * 初期状態
 */
private String startStatus;

/**
 * 受理状態の集合
 */
private Set<String> acceptanceStatusSet;

/**
 * 有限オートマトンの定義に沿った内容かどうかを判定する関数。
 * @return 定義に問題が無ければ、true
 * @throws IllegalArgumentException 定義に問題があれば、対応する例外を発生させる。
 */
private boolean isLegitimateAutomaton() throws IllegalArgumentException{
	for(Iterator<String> statusIterator = this.statusSet.iterator(); statusIterator.hasNext(); ) {
		String status = statusIterator.next();
		if(!this.deltaMap.containsKey(status)) {
			throw new IllegalDeltaException("状態" + status + "からの遷移が定義されていません。");
		}
		for(Iterator<Character> sigmaIterator = this.sigmaSet.iterator(); sigmaIterator.hasNext(); ) {
			char symbol = sigmaIterator.next();
			Map<Character, String> innerDeltaMap = this.deltaMap.get(status);
			if(!innerDeltaMap.containsKey(symbol)) {
				throw new IllegalDeltaException("状態" + status + "から、記号" + symbol + "による遷移が定義されていません。");
			}
			String nextStatus = innerDeltaMap.get(symbol);
			if(!this.statusSet.contains(nextStatus)) {
				throw new IllegalDeltaException("状態" + status + "から、記号" + symbol + "による遷移先" + nextStatus + "が状態の集合に含まれていません。");
			}
		}
	}

	if(!this.statusSet.contains(this.startStatus)) {
		throw new IllegalStartStatusException("初期状態" + this.startStatus + "が状態の集合に含まれていません。");
	}

	return true;
}

/**
 * 不必要な定義を削除する関数。
 * 削除対象は、到達不可な状態、未使用の状態遷移の定義、未使用の受理状態。
 */
private void removeUnusedDefinition() {
	Set<String> newStatusSet = new HashSet<>();
	newStatusSet.add(this.startStatus);
	int old_size, new_size;
	do {
		old_size = newStatusSet.size();
		Set<String> addingStatusSet = new HashSet<>();
		for(Iterator<String> newStatusIterator = newStatusSet.iterator(); newStatusIterator.hasNext(); ) {
			String status = newStatusIterator.next();
			for(Iterator<Character> sigmaIterator = this.sigmaSet.iterator(); sigmaIterator.hasNext(); ) {
				char symbol = sigmaIterator.next();
				String nextStatus = delta(status, symbol);
				addingStatusSet.add(nextStatus);
			}
		}
		newStatusSet.addAll(addingStatusSet);
		new_size = newStatusSet.size();
	}while(old_size < new_size);
	this.statusSet = newStatusSet;

	Map<String, Map<Character, String>> newDeltaMap = new HashMap<>();
	for(Iterator<String> statusIterator = this.statusSet.iterator(); statusIterator.hasNext(); ) {
		String status = statusIterator.next();
		Map<Character, String> newInnerDeltaMap = new HashMap<>();
		for(Iterator<Character> sigmaIterator = this.sigmaSet.iterator(); sigmaIterator.hasNext(); ) {
			char symbol = sigmaIterator.next();
			String nextStatus = delta(status, symbol);
			newInnerDeltaMap.put(symbol, nextStatus);
		}
		newDeltaMap.put(status, newInnerDeltaMap);
	}
	this.deltaMap = newDeltaMap;

	Set<String> removingAcceptanceSet = new HashSet<>();
	for(Iterator<String> acceptanceStatusIterator = this.acceptanceStatusSet.iterator(); acceptanceStatusIterator.hasNext(); ) {
		String status = acceptanceStatusIterator.next();
		if(!this.statusSet.contains(status)) {
			removingAcceptanceSet.add(status);
		}
	}
	this.acceptanceStatusSet.removeAll(removingAcceptanceSet);
}

/**
 * 有限オートマトンのインスタンスを生成するコンストラクタ。
 * @param statusSet 状態の集合
 * @param sigmaSet 入力記号の集合
 * @param deltaMap 状態遷移関数の定義
 * @param startStatus 初期状態
 * @param acceptanceStatusSet 受理状態の集合
 * @throws IllegalArgumentException 入力に問題があれば、対応する例外を発生させる。
 */
public FiniteAutomaton(
		Set<String> statusSet,
		Set<Character> sigmaSet,
		Map<String, Map<Character, String>> deltaMap,
		String startStatus,
		Set<String> acceptanceStatusSet
) throws IllegalArgumentException {
	if(statusSet == null) {
		throw new IllegalArgumentException("状態の集合がnullです。");
	}
	if(sigmaSet == null) {
		throw new IllegalArgumentException("入力記号の集合がnullです。");
	}
	if(deltaMap == null) {
		throw new IllegalArgumentException("状態遷移関数の定義がnullです。");
	}
	if(startStatus == null) {
		throw new IllegalArgumentException("初期状態がnullです。");
	}
	if(acceptanceStatusSet == null) {
		throw new IllegalArgumentException("受理状態の集合がnullです。");
	}

	this.statusSet = statusSet;
	this.sigmaSet = sigmaSet;
	this.deltaMap = deltaMap;
	this.startStatus = startStatus;
	this.acceptanceStatusSet = acceptanceStatusSet;

	if(isLegitimateAutomaton()) {
		removeUnusedDefinition();
	}
}

/**
 * 現状態nowStatus、記号symbolによる次状態δ(nowStatus, symbol)を返す関数。
 * @param nowStatus 現状態
 * @param symbol 入力記号
 * @return 次状態δ(nowStatus, symbol)
 * @throws IllegalArgumentException 入力に問題があれば、対応する例外を発生させる。
 */
public String delta(String nowStatus, char symbol) throws IllegalArgumentException{
	if(!this.statusSet.contains(nowStatus)) {
		throw new NotExistsStatusException("入力された状態" + nowStatus + "が状態の集合に含まれていません。");
	}
	if(!this.sigmaSet.contains(symbol)) {
		throw new NotExistsInputSymbolException("入力された記号" + symbol + "が入力記号の集合に含まれていません。");
	}
	return this.deltaMap.get(nowStatus).get(symbol);
}

/**
 * 現状態nowStatus、列lineによる次状態δ(nowStatus, line)を返す関数。
 * @param nowStatus 現状態
 * @param line 入力列
 * @return 次状態δ(nowStatus, line)
 * @throws IllegalArgumentException 入力に問題があれば、対応する例外を発生させる。
 */
public String delta(String nowStatus, String line) throws IllegalArgumentException{
	String status = nowStatus;
	for(int i = 0; i < line.length(); i++) {
		status = delta(status, line.charAt(i));
	}
	return status;
}

/**
 * 列lineが受理されるかどうかを判定する関数。
 * @param line 入力列
 * @return lineが受理されればtrue、受理されなければfalse
 * @throws IllegalArgumentException 入力に問題があれば、対応する例外を発生させる。
 */
public boolean isAccept(String line) throws IllegalArgumentException{
	String status = delta(this.startStatus, line);
	return this.acceptanceStatusSet.contains(status);
}

/**
 * 直積オートマトン生成時のフラグ、両オートマトンで受理されるものを受理する
 */
public static final int ACCEPT_AND = 0;

/**
 * 直積オートマトン生成時のフラグ、少なくとも片方の有限オートマトンで受理されるものを受理する
 */
public static final int ACCEPT_OR = 1;

/**
 * 直積オートマトンを生成する関数。
 * @param M1 直積させる有限オートマトンのインスタンス
 * @param M2 直積させる有限オートマトンのインスタンス
 * @param acceptanceSetFlug 直積オートマトンの受理状態に関するフラグ、0もしくは1
 * @return 直積オートマトンのインスタンス
 * @throws IllegalArgumentException 入力に問題があれば、対応する例外を発生させる
 */
public static FiniteAutomaton makeProductAutomaton(
		FiniteAutomaton M1,
		FiniteAutomaton M2,
		int acceptanceSetFlug
) throws IllegalArgumentException{
	if(!M1.sigmaSet.containsAll(M2.sigmaSet)) {
		throw new DifferentInputSymbolException("直積させる2つの有限オートマトンの入力記号の集合が異なります。");
	}
	if(!M2.sigmaSet.containsAll(M1.sigmaSet)) {
		throw new DifferentInputSymbolException("直積させる2つの有限オートマトンの入力記号の集合が異なります。");
	}
	if(acceptanceSetFlug < 0 || acceptanceSetFlug > 1) {
		throw new IllegalArgumentException("受理状態に関するフラグが不正です。");
	}
	return FiniteAutomaton.makeProductAutomaton(
			M1,
			M2,
			M1.startStatus,
			M2.startStatus,
			acceptanceSetFlug
	);
}

/**
 * 同じ言語を認識する最小の有限オートマトンへ変形する関数。
 */
public void shrinkAutomaton() {
	Set<Set<String>> equivStatusSetSet = getEquivStatusSetSet();
	shrinkAllEquivStatus(equivStatusSetSet);
}

/**
 * 直積オートマトンを生成する関数。
 * @param M1 直積させる有限オートマトンのインスタンス
 * @param M2 直積させる有限オートマトンのインスタンス
 * @param startStatus1 M1の初期状態
 * @param startStatus2 M2の初期状態
 * @param acceptanceSetFlug 受理状態に関するフラグ、0もしくは1
 * @return M1とM2の直積オートマトン
 */
private static FiniteAutomaton makeProductAutomaton(
		FiniteAutomaton M1,
		FiniteAutomaton M2,
		String startStatus1,
		String startStatus2,
		int acceptanceSetFlug
) {
	Set<String> newStatusSet = new HashSet<>();
	Map<String, Map<Character, String>> newDeltaMap = new HashMap<>();
	for(Iterator<String> status1Iterator = M1.statusSet.iterator(); status1Iterator.hasNext(); ) {
		String status1 = status1Iterator.next();
		for(Iterator<String> status2Iterator = M2.statusSet.iterator(); status2Iterator.hasNext(); ) {
			String status2 = status2Iterator.next();
			String newStatus = "(" + status1 + ", " + status2 + ")";
			newStatusSet.add(newStatus);

			Map<Character, String> newInnerDeltaMap = new HashMap<>();
			for(Iterator<Character> sigmaIterator = M1.sigmaSet.iterator(); sigmaIterator.hasNext(); ) {
				char symbol = sigmaIterator.next();
				String nextStatus1 = M1.delta(status1, symbol);
				String nextStatus2 = M2.delta(status2, symbol);
				String newNextStatus = "(" + nextStatus1 + ", " + nextStatus2 + ")";
				newInnerDeltaMap.put(symbol, newNextStatus);
			}
			newDeltaMap.put(newStatus, newInnerDeltaMap);
		}
	}

	String newStartStatus = "(" + startStatus1 + ", " + startStatus2 + ")";

	Set<String> newAcceptanceStatusSet = new HashSet<>();
	if(acceptanceSetFlug == FiniteAutomaton.ACCEPT_AND) {
		for(Iterator<String> acceptanceStatus1Iterator = M1.acceptanceStatusSet.iterator(); acceptanceStatus1Iterator.hasNext(); ) {
			String acceptanceStatus1 = acceptanceStatus1Iterator.next();
			for(Iterator<String> acceptanceStatus2Iterator = M2.acceptanceStatusSet.iterator(); acceptanceStatus2Iterator.hasNext(); ) {
				String acceptanceStatus2 = acceptanceStatus2Iterator.next();
				String newAcceptanceStatus = "(" + acceptanceStatus1 + ", " + acceptanceStatus2 + ")";
				newAcceptanceStatusSet.add(newAcceptanceStatus);
			}
		}
	}else if(acceptanceSetFlug == FiniteAutomaton.ACCEPT_OR) {
		for(Iterator<String> status1Iterator = M1.statusSet.iterator(); status1Iterator.hasNext(); ) {
			String status1 = status1Iterator.next();
			for(Iterator<String> acceptanceStatus2Iterator = M2.acceptanceStatusSet.iterator(); acceptanceStatus2Iterator.hasNext(); ) {
				String acceptanceStatus2 = acceptanceStatus2Iterator.next();
				String newAcceptanceStatus = "(" + status1 + ", " + acceptanceStatus2 + ")";
				newAcceptanceStatusSet.add(newAcceptanceStatus);
			}
		}
		for(Iterator<String> acceptanceStatus1Iterator = M1.acceptanceStatusSet.iterator(); acceptanceStatus1Iterator.hasNext(); ) {
			String acceptanceStatus1 = acceptanceStatus1Iterator.next();
			for(Iterator<String> status2Iterator = M2.statusSet.iterator(); status2Iterator.hasNext(); ) {
				String status2 = status2Iterator.next();
				String newAcceptanceStatus = "(" + acceptanceStatus1 + ", " + status2 + ")";
				newAcceptanceStatusSet.add(newAcceptanceStatus);

			}
		}
	}

	return new FiniteAutomaton(
			newStatusSet,
			M1.sigmaSet,
			newDeltaMap,
			newStartStatus,
			newAcceptanceStatusSet
	);
}

/**
 * 2状態が等価かどうかを判定する関数。
 * @param status1 等価判定を行う状態
 * @param status2 等価判定を行う状態
 * @return 2状態が等価であればtrue、非等価であればfalse
 */
private boolean isEquivStatus(String status1, String status2) {
	FiniteAutomaton M = FiniteAutomaton.makeProductAutomaton(
			this,
			this,
			status1,
			status2,
			FiniteAutomaton.ACCEPT_AND
	);

	String[] statusArray = new String[this.statusSet.size()];
	this.statusSet.toArray(statusArray);

	for(int i = 0; i < statusArray.length; i++) {
		for(int j = 0; j < statusArray.length; j++) {
			String status = "(" + statusArray[i] + ", " + statusArray[j] + ")";
			if(M.statusSet.contains(status)) {
				if(this.acceptanceStatusSet.contains(statusArray[i]) != this.acceptanceStatusSet.contains(statusArray[j])) {
					return false;
				}
			}
		}
	}

	return true;
}

/**
 * 等価な状態の集合の集合を得る関数
 * @return 等価な状態の集合の集合
 */
private Set<Set<String>> getEquivStatusSetSet(){
	Set<Set<String>> equivStatusSetSet = new HashSet<>();
	Set<String> checkedStatusSet = new HashSet<>();

	String[] statusArray = new String[this.statusSet.size()];
	this.statusSet.toArray(statusArray);

	for(int i = 0; i < statusArray.length; i++) {
		if(checkedStatusSet.contains(statusArray[i])) {
			continue;
		}
		Set<String> equivStatusSet = new HashSet<>();
		equivStatusSet.add(statusArray[i]);
		checkedStatusSet.add(statusArray[i]);
		for(int j = 0; j < statusArray.length; j++) {
			if(checkedStatusSet.contains(statusArray[j])) {
				continue;
			}
			if(isEquivStatus(statusArray[i], statusArray[j])) {
				equivStatusSet.add(statusArray[j]);
			}
		}
		equivStatusSetSet.add(equivStatusSet);
		checkedStatusSet.addAll(equivStatusSet);
	}

	return equivStatusSetSet;
}

/**
 * ある等価な状態の集合を縮小する関数。
 * @param equivStatusSet 縮小を行う等価な状態の集合
 */
private void shrinkEquivStatus(Set<String> equivStatusSet) {
	Set<String> newStatusSet = new HashSet<>();
	Map<String, Map<Character, String>> newDeltaMap = new HashMap<>();
	String newStartStatus = "";
	Set<String> newAcceptanceStatusSet = new HashSet<>();

	for(Iterator<String> it = this.statusSet.iterator(); it.hasNext(); ) {
		String status = it.next();
		if(!equivStatusSet.contains(status)) {
			newStatusSet.add(status);
		}
	}
	String equivStatusString = "[";
	for(Iterator<String> equivStatusIterator = equivStatusSet.iterator(); equivStatusIterator.hasNext(); ) {
		equivStatusString += equivStatusIterator.next();
		if(equivStatusIterator.hasNext()) {
			equivStatusString += ", ";
		}
	}
	equivStatusString += "]";
	newStatusSet.add(equivStatusString);

	for(Iterator<String> statusIterator = this.statusSet.iterator(); statusIterator.hasNext(); ) {
		String status = statusIterator.next();
		Map<Character, String> newInnerDeltaMap = new HashMap<>();
		for(Iterator<Character> sigmaIterator = this.sigmaSet.iterator(); sigmaIterator.hasNext(); ) {
			char symbol = sigmaIterator.next();
			String nextStatus = delta(status, symbol);
			if(equivStatusSet.contains(nextStatus)) {
				newInnerDeltaMap.put(symbol, equivStatusString);
			}else {
				newInnerDeltaMap.put(symbol, nextStatus);
			}
		}
		if(equivStatusSet.contains(status)) {
			newDeltaMap.put(equivStatusString, newInnerDeltaMap);
		}else {
			newDeltaMap.put(status, newInnerDeltaMap);
		}
	}

	if(equivStatusSet.contains(this.startStatus)) {
		newStartStatus = equivStatusString;
	}else {
		newStartStatus = this.startStatus;
	}

	for(Iterator<String> acceptanceStatusIterator = this.acceptanceStatusSet.iterator(); acceptanceStatusIterator.hasNext(); ) {
		String acceptanceStatus = acceptanceStatusIterator.next();
		if(equivStatusSet.contains(acceptanceStatus)) {
			newAcceptanceStatusSet.add(equivStatusString);
		}else {
			newAcceptanceStatusSet.add(acceptanceStatus);
		}
	}

	this.statusSet = newStatusSet;
	this.deltaMap = newDeltaMap;
	this.startStatus = newStartStatus;
	this.acceptanceStatusSet = newAcceptanceStatusSet;
}

/**
 * 全ての等価な状態の集合を縮小する関数。
 * @param equivStatusSetSet 等価な状態の集合の集合
 */
private void shrinkAllEquivStatus(Set<Set<String>> equivStatusSetSet) {
	for(Iterator<Set<String>> equivStatusSetIterator = equivStatusSetSet.iterator(); equivStatusSetIterator.hasNext(); ) {
		Set<String> equivStatusSet = equivStatusSetIterator.next();
		if(equivStatusSet.size() > 1) {
			shrinkEquivStatus(equivStatusSet);
		}
	}
}

/**
 * 有限オートマトンの各情報をコンソールに表示する関数。
 */
public void showAutomatonInformation() {
	System.out.println("状態：");
	for(Iterator<String> statusIterator = this.statusSet.iterator(); statusIterator.hasNext(); ) {
		System.out.println("\t" + statusIterator.next());
	}
	System.out.println("入力記号：");
	System.out.print("\t{");
	for(Iterator<Character> sigmaIterator = this.sigmaSet.iterator(); sigmaIterator.hasNext(); ) {
		System.out.print(sigmaIterator.next());
		if(sigmaIterator.hasNext()) {
			System.out.print(", ");
		}
	}
	System.out.println("}");
	System.out.println("状態遷移関数：");
	for(Iterator<String> statusIterator = this.statusSet.iterator(); statusIterator.hasNext(); ) {
		String nowStatus = statusIterator.next();
		for(Iterator<Character> sigmaIterator = this.sigmaSet.iterator(); sigmaIterator.hasNext(); ) {
			char a = sigmaIterator.next();
			System.out.println("\tδ(" + nowStatus + ", " + a + ") = " + delta(nowStatus, a));
		}
	}
	System.out.println("初期状態：" + this.startStatus);
	System.out.println("受理状態：");
	for(Iterator<String> acceptanceStatusIterator = this.acceptanceStatusSet.iterator(); acceptanceStatusIterator.hasNext(); ) {
		System.out.println("\t" + acceptanceStatusIterator.next());
	}
}

状態：
	s_1
	s_0
	s_3
	s_2
入力記号：
	{0, 1}
状態遷移関数：
	δ(s_1, 0) = s_0
	δ(s_1, 1) = s_3
	δ(s_0, 0) = s_1
	δ(s_0, 1) = s_2
	δ(s_3, 0) = s_2
	δ(s_3, 1) = s_1
	δ(s_2, 0) = s_3
	δ(s_2, 1) = s_0
初期状態：s_0
受理状態：
	s_0

package model.exception;

/**
 * 直積オートマトン生成時の入力記号に関する例外。
 * @author シノ
 *
 */
public class DifferentInputSymbolException extends IllegalArgumentException {

	public DifferentInputSymbolException(String msg) {
		super(msg);
	}
}

package model;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;

import model.exception.DifferentInputSymbolException;
import model.exception.IllegalDeltaException;
import model.exception.IllegalStartStatusException;
import model.exception.NotExistsInputSymbolException;
import model.exception.NotExistsStatusException;

/**
 * 有限オートマトンを表現するクラス。
 * @author シノ
 *
 */
public class FiniteAutomaton {
	/**
	 * 直積オートマトン生成時のフラグ、両オートマトンで受理されるものを受理する
	 */
	public static final int ACCEPT_AND = 0;

	/**
	 * 直積オートマトン生成時のフラグ、少なくとも片方の有限オートマトンで受理されるものを受理する
	 */
	public static final int ACCEPT_OR = 1;

	/**
	 * 状態の集合
	 */
	private Set<String> statusSet;

	/**
	 * 入力記号の集合
	 */
	private Set<Character> sigmaSet;

	/**
	 * 状態遷移関数の定義
	 */
	private Map<String, Map<Character, String>> deltaMap;

	/**
	 * 初期状態
	 */
	private String startStatus;

	/**
	 * 受理状態の集合
	 */
	private Set<String> acceptanceStatusSet;

	/**
	 * 有限オートマトンのインスタンスを生成するコンストラクタ。
	 * @param statusSet 状態の集合
	 * @param sigmaSet 入力記号の集合
	 * @param deltaMap 状態遷移関数の定義
	 * @param startStatus 初期状態
	 * @param acceptanceStatusSet 受理状態の集合
	 * @throws IllegalArgumentException 入力に問題があれば、対応する例外を発生させる。
	 */
	public FiniteAutomaton(
			Set<String> statusSet,
			Set<Character> sigmaSet,
			Map<String, Map<Character, String>> deltaMap,
			String startStatus,
			Set<String> acceptanceStatusSet
	) throws IllegalArgumentException {
		if(statusSet == null) {
			throw new IllegalArgumentException("状態の集合がnullです。");
		}
		if(sigmaSet == null) {
			throw new IllegalArgumentException("入力記号の集合がnullです。");
		}
		if(deltaMap == null) {
			throw new IllegalArgumentException("状態遷移関数の定義がnullです。");
		}
		if(startStatus == null) {
			throw new IllegalArgumentException("初期状態がnullです。");
		}
		if(acceptanceStatusSet == null) {
			throw new IllegalArgumentException("受理状態の集合がnullです。");
		}

		this.statusSet = statusSet;
		this.sigmaSet = sigmaSet;
		this.deltaMap = deltaMap;
		this.startStatus = startStatus;
		this.acceptanceStatusSet = acceptanceStatusSet;

		if(isLegitimateAutomaton()) {
			removeUnusedDefinition();
		}
	}

	/**
	 * 現状態nowStatus、記号symbolによる次状態δ(nowStatus, symbol)を返す関数。
	 * @param nowStatus 現状態
	 * @param symbol 入力記号
	 * @return 次状態δ(nowStatus, symbol)
	 * @throws IllegalArgumentException 入力に問題があれば、対応する例外を発生させる。
	 */
	public String delta(String nowStatus, char symbol) throws IllegalArgumentException{
		if(!this.statusSet.contains(nowStatus)) {
			throw new NotExistsStatusException("入力された状態" + nowStatus + "が状態の集合に含まれていません。");
		}
		if(!this.sigmaSet.contains(symbol)) {
			throw new NotExistsInputSymbolException("入力された記号" + symbol + "が入力記号の集合に含まれていません。");
		}
		return this.deltaMap.get(nowStatus).get(symbol);
	}

	/**
	 * 現状態nowStatus、列lineによる次状態δ(nowStatus, line)を返す関数。
	 * @param nowStatus 現状態
	 * @param line 入力列
	 * @return 次状態δ(nowStatus, line)
	 * @throws IllegalArgumentException 入力に問題があれば、対応する例外を発生させる。
	 */
	public String delta(String nowStatus, String line) throws IllegalArgumentException{
		String status = nowStatus;
		for(int i = 0; i < line.length(); i++) {
			status = delta(status, line.charAt(i));
		}
		return status;
	}

	/**
	 * 列lineが受理されるかどうかを判定する関数。
	 * @param line 入力列
	 * @return lineが受理されればtrue、受理されなければfalse
	 * @throws IllegalArgumentException 入力に問題があれば、対応する例外を発生させる。
	 */
	public boolean isAccept(String line) throws IllegalArgumentException{
		String status = delta(this.startStatus, line);
		return this.acceptanceStatusSet.contains(status);
	}

	/**
	 * 直積オートマトンを生成する関数。
	 * @param M1 直積させる有限オートマトンのインスタンス
	 * @param M2 直積させる有限オートマトンのインスタンス
	 * @param acceptanceSetFlug 直積オートマトンの受理状態に関するフラグ、0もしくは1
	 * @return 直積オートマトンのインスタンス
	 * @throws IllegalArgumentException 入力に問題があれば、対応する例外を発生させる
	 */
	public static FiniteAutomaton makeProductAutomaton(
			FiniteAutomaton M1,
			FiniteAutomaton M2,
			int acceptanceSetFlug
	) throws IllegalArgumentException{
		if(!M1.sigmaSet.containsAll(M2.sigmaSet)) {
			throw new DifferentInputSymbolException("直積させる2つの有限オートマトンの入力記号の集合が異なります。");
		}
		if(!M2.sigmaSet.containsAll(M1.sigmaSet)) {
			throw new DifferentInputSymbolException("直積させる2つの有限オートマトンの入力記号の集合が異なります。");
		}
		if(acceptanceSetFlug < 0 || acceptanceSetFlug > 1) {
			throw new IllegalArgumentException("受理状態に関するフラグが不正です。");
		}
		return FiniteAutomaton.makeProductAutomaton(
				M1,
				M2,
				M1.startStatus,
				M2.startStatus,
				acceptanceSetFlug
		);
	}

	/**
	 * 同じ言語を認識する最小の有限オートマトンへ変形する関数。
	 */
	public void shrinkAutomaton() {
		Set<Set<String>> equivStatusSetSet = getEquivStatusSetSet();
		shrinkAllEquivStatus(equivStatusSetSet);
	}

	/**
	 * 有限オートマトンの各情報をコンソールに表示する関数。
	 */
	public void showAutomatonInformation() {
		System.out.println("状態：");
		for(Iterator<String> statusIterator = this.statusSet.iterator(); statusIterator.hasNext(); ) {
			System.out.println("\t" + statusIterator.next());
		}
		System.out.println("入力記号：");
		System.out.print("\t{");
		for(Iterator<Character> sigmaIterator = this.sigmaSet.iterator(); sigmaIterator.hasNext(); ) {
			System.out.print(sigmaIterator.next());
			if(sigmaIterator.hasNext()) {
				System.out.print(", ");
			}
		}
		System.out.println("}");
		System.out.println("状態遷移関数：");
		for(Iterator<String> statusIterator = this.statusSet.iterator(); statusIterator.hasNext(); ) {
			String nowStatus = statusIterator.next();
			for(Iterator<Character> sigmaIterator = this.sigmaSet.iterator(); sigmaIterator.hasNext(); ) {
				char a = sigmaIterator.next();
				System.out.println("\tδ(" + nowStatus + ", " + a + ") = " + delta(nowStatus, a));
			}
		}
		System.out.println("初期状態：" + this.startStatus);
		System.out.println("受理状態：");
		for(Iterator<String> acceptanceStatusIterator = this.acceptanceStatusSet.iterator(); acceptanceStatusIterator.hasNext(); ) {
			System.out.println("\t" + acceptanceStatusIterator.next());
		}
	}

	/**
	 * 有限オートマトンの定義に沿った内容かどうかを判定する関数。
	 * @return 定義に問題が無ければ、true
	 * @throws IllegalArgumentException 定義に問題があれば、対応する例外を発生させる。
	 */
	private boolean isLegitimateAutomaton() throws IllegalArgumentException{
		for(Iterator<String> statusIterator = this.statusSet.iterator(); statusIterator.hasNext(); ) {
			String status = statusIterator.next();
			if(!this.deltaMap.containsKey(status)) {
				throw new IllegalDeltaException("状態" + status + "からの遷移が定義されていません。");
			}
			for(Iterator<Character> sigmaIterator = this.sigmaSet.iterator(); sigmaIterator.hasNext(); ) {
				char symbol = sigmaIterator.next();
				Map<Character, String> innerDeltaMap = this.deltaMap.get(status);
				if(!innerDeltaMap.containsKey(symbol)) {
					throw new IllegalDeltaException("状態" + status + "から、記号" + symbol + "による遷移が定義されていません。");
				}
				String nextStatus = innerDeltaMap.get(symbol);
				if(!this.statusSet.contains(nextStatus)) {
					throw new IllegalDeltaException("状態" + status + "から、記号" + symbol + "による遷移先" + nextStatus + "が状態の集合に含まれていません。");
				}
			}
		}

		if(!this.statusSet.contains(this.startStatus)) {
			throw new IllegalStartStatusException("初期状態" + this.startStatus + "が状態の集合に含まれていません。");
		}

		return true;
	}

	/**
	 * 不必要な定義を削除する関数。
	 * 削除対象は、到達不可な状態、未使用の状態遷移の定義、未使用の受理状態。
	 */
	private void removeUnusedDefinition() {
		Set<String> newStatusSet = new HashSet<>();
		newStatusSet.add(this.startStatus);
		int old_size, new_size;
		do {
			old_size = newStatusSet.size();
			Set<String> addingStatusSet = new HashSet<>();
			for(Iterator<String> newStatusIterator = newStatusSet.iterator(); newStatusIterator.hasNext(); ) {
				String status = newStatusIterator.next();
				for(Iterator<Character> sigmaIterator = this.sigmaSet.iterator(); sigmaIterator.hasNext(); ) {
					char symbol = sigmaIterator.next();
					String nextStatus = delta(status, symbol);
					addingStatusSet.add(nextStatus);
				}
			}
			newStatusSet.addAll(addingStatusSet);
			new_size = newStatusSet.size();
		}while(old_size < new_size);
		this.statusSet = newStatusSet;

		Map<String, Map<Character, String>> newDeltaMap = new HashMap<>();
		for(Iterator<String> statusIterator = this.statusSet.iterator(); statusIterator.hasNext(); ) {
			String status = statusIterator.next();
			Map<Character, String> newInnerDeltaMap = new HashMap<>();
			for(Iterator<Character> sigmaIterator = this.sigmaSet.iterator(); sigmaIterator.hasNext(); ) {
				char symbol = sigmaIterator.next();
				String nextStatus = delta(status, symbol);
				newInnerDeltaMap.put(symbol, nextStatus);
			}
			newDeltaMap.put(status, newInnerDeltaMap);
		}
		this.deltaMap = newDeltaMap;

		Set<String> removingAcceptanceSet = new HashSet<>();
		for(Iterator<String> acceptanceStatusIterator = this.acceptanceStatusSet.iterator(); acceptanceStatusIterator.hasNext(); ) {
			String status = acceptanceStatusIterator.next();
			if(!this.statusSet.contains(status)) {
				removingAcceptanceSet.add(status);
			}
		}
		this.acceptanceStatusSet.removeAll(removingAcceptanceSet);
	}

	/**
	 * 直積オートマトンを生成する関数。
	 * @param M1 直積させる有限オートマトンのインスタンス
	 * @param M2 直積させる有限オートマトンのインスタンス
	 * @param startStatus1 M1の初期状態
	 * @param startStatus2 M2の初期状態
	 * @param acceptanceSetFlug 受理状態に関するフラグ、0もしくは1
	 * @return M1とM2の直積オートマトン
	 */
	private static FiniteAutomaton makeProductAutomaton(
			FiniteAutomaton M1,
			FiniteAutomaton M2,
			String startStatus1,
			String startStatus2,
			int acceptanceSetFlug
	) {
		Set<String> newStatusSet = new HashSet<>();
		Map<String, Map<Character, String>> newDeltaMap = new HashMap<>();
		for(Iterator<String> status1Iterator = M1.statusSet.iterator(); status1Iterator.hasNext(); ) {
			String status1 = status1Iterator.next();
			for(Iterator<String> status2Iterator = M2.statusSet.iterator(); status2Iterator.hasNext(); ) {
				String status2 = status2Iterator.next();
				String newStatus = "(" + status1 + ", " + status2 + ")";
				newStatusSet.add(newStatus);

				Map<Character, String> newInnerDeltaMap = new HashMap<>();
				for(Iterator<Character> sigmaIterator = M1.sigmaSet.iterator(); sigmaIterator.hasNext(); ) {
					char symbol = sigmaIterator.next();
					String nextStatus1 = M1.delta(status1, symbol);
					String nextStatus2 = M2.delta(status2, symbol);
					String newNextStatus = "(" + nextStatus1 + ", " + nextStatus2 + ")";
					newInnerDeltaMap.put(symbol, newNextStatus);
				}
				newDeltaMap.put(newStatus, newInnerDeltaMap);
			}
		}

		String newStartStatus = "(" + startStatus1 + ", " + startStatus2 + ")";

		Set<String> newAcceptanceStatusSet = new HashSet<>();
		if(acceptanceSetFlug == FiniteAutomaton.ACCEPT_AND) {
			for(Iterator<String> acceptanceStatus1Iterator = M1.acceptanceStatusSet.iterator(); acceptanceStatus1Iterator.hasNext(); ) {
				String acceptanceStatus1 = acceptanceStatus1Iterator.next();
				for(Iterator<String> acceptanceStatus2Iterator = M2.acceptanceStatusSet.iterator(); acceptanceStatus2Iterator.hasNext(); ) {
					String acceptanceStatus2 = acceptanceStatus2Iterator.next();
					String newAcceptanceStatus = "(" + acceptanceStatus1 + ", " + acceptanceStatus2 + ")";
					newAcceptanceStatusSet.add(newAcceptanceStatus);
				}
			}
		}else if(acceptanceSetFlug == FiniteAutomaton.ACCEPT_OR) {
			for(Iterator<String> status1Iterator = M1.statusSet.iterator(); status1Iterator.hasNext(); ) {
				String status1 = status1Iterator.next();
				for(Iterator<String> acceptanceStatus2Iterator = M2.acceptanceStatusSet.iterator(); acceptanceStatus2Iterator.hasNext(); ) {
					String acceptanceStatus2 = acceptanceStatus2Iterator.next();
					String newAcceptanceStatus = "(" + status1 + ", " + acceptanceStatus2 + ")";
					newAcceptanceStatusSet.add(newAcceptanceStatus);
				}
			}
			for(Iterator<String> acceptanceStatus1Iterator = M1.acceptanceStatusSet.iterator(); acceptanceStatus1Iterator.hasNext(); ) {
				String acceptanceStatus1 = acceptanceStatus1Iterator.next();
				for(Iterator<String> status2Iterator = M2.statusSet.iterator(); status2Iterator.hasNext(); ) {
					String status2 = status2Iterator.next();
					String newAcceptanceStatus = "(" + acceptanceStatus1 + ", " + status2 + ")";
					newAcceptanceStatusSet.add(newAcceptanceStatus);

				}
			}
		}

		return new FiniteAutomaton(
				newStatusSet,
				M1.sigmaSet,
				newDeltaMap,
				newStartStatus,
				newAcceptanceStatusSet
		);
	}

	/**
	 * 2状態が等価かどうかを判定する関数。
	 * @param status1 等価判定を行う状態
	 * @param status2 等価判定を行う状態
	 * @return 2状態が等価であればtrue、非等価であればfalse
	 */
	private boolean isEquivStatus(String status1, String status2) {
		FiniteAutomaton M = FiniteAutomaton.makeProductAutomaton(
				this,
				this,
				status1,
				status2,
				FiniteAutomaton.ACCEPT_AND
		);

		String[] statusArray = new String[this.statusSet.size()];
		this.statusSet.toArray(statusArray);

		for(int i = 0; i < statusArray.length; i++) {
			for(int j = 0; j < statusArray.length; j++) {
				String status = "(" + statusArray[i] + ", " + statusArray[j] + ")";
				if(M.statusSet.contains(status)) {
					if(this.acceptanceStatusSet.contains(statusArray[i]) != this.acceptanceStatusSet.contains(statusArray[j])) {
						return false;
					}
				}
			}
		}

		return true;
	}

	/**
	 * 等価な状態の集合の集合を得る関数
	 * @return 等価な状態の集合の集合
	 */
	private Set<Set<String>> getEquivStatusSetSet(){
		Set<Set<String>> equivStatusSetSet = new HashSet<>();
		Set<String> checkedStatusSet = new HashSet<>();

		String[] statusArray = new String[this.statusSet.size()];
		this.statusSet.toArray(statusArray);

		for(int i = 0; i < statusArray.length; i++) {
			if(checkedStatusSet.contains(statusArray[i])) {
				continue;
			}
			Set<String> equivStatusSet = new HashSet<>();
			equivStatusSet.add(statusArray[i]);
			checkedStatusSet.add(statusArray[i]);
			for(int j = 0; j < statusArray.length; j++) {
				if(checkedStatusSet.contains(statusArray[j])) {
					continue;
				}
				if(isEquivStatus(statusArray[i], statusArray[j])) {
					equivStatusSet.add(statusArray[j]);
				}
			}
			equivStatusSetSet.add(equivStatusSet);
			checkedStatusSet.addAll(equivStatusSet);
		}

		return equivStatusSetSet;
	}

	/**
	 * ある等価な状態の集合を縮小する関数。
	 * @param equivStatusSet 縮小を行う等価な状態の集合
	 */
	private void shrinkEquivStatus(Set<String> equivStatusSet) {
		Set<String> newStatusSet = new HashSet<>();
		Map<String, Map<Character, String>> newDeltaMap = new HashMap<>();
		String newStartStatus = "";
		Set<String> newAcceptanceStatusSet = new HashSet<>();

		for(Iterator<String> it = this.statusSet.iterator(); it.hasNext(); ) {
			String status = it.next();
			if(!equivStatusSet.contains(status)) {
				newStatusSet.add(status);
			}
		}
		String equivStatusString = "[";
		for(Iterator<String> equivStatusIterator = equivStatusSet.iterator(); equivStatusIterator.hasNext(); ) {
			equivStatusString += equivStatusIterator.next();
			if(equivStatusIterator.hasNext()) {
				equivStatusString += ", ";
			}
		}
		equivStatusString += "]";
		newStatusSet.add(equivStatusString);

		for(Iterator<String> statusIterator = this.statusSet.iterator(); statusIterator.hasNext(); ) {
			String status = statusIterator.next();
			Map<Character, String> newInnerDeltaMap = new HashMap<>();
			for(Iterator<Character> sigmaIterator = this.sigmaSet.iterator(); sigmaIterator.hasNext(); ) {
				char symbol = sigmaIterator.next();
				String nextStatus = delta(status, symbol);
				if(equivStatusSet.contains(nextStatus)) {
					newInnerDeltaMap.put(symbol, equivStatusString);
				}else {
					newInnerDeltaMap.put(symbol, nextStatus);
				}
			}
			if(equivStatusSet.contains(status)) {
				newDeltaMap.put(equivStatusString, newInnerDeltaMap);
			}else {
				newDeltaMap.put(status, newInnerDeltaMap);
			}
		}

		if(equivStatusSet.contains(this.startStatus)) {
			newStartStatus = equivStatusString;
		}else {
			newStartStatus = this.startStatus;
		}

		for(Iterator<String> acceptanceStatusIterator = this.acceptanceStatusSet.iterator(); acceptanceStatusIterator.hasNext(); ) {
			String acceptanceStatus = acceptanceStatusIterator.next();
			if(equivStatusSet.contains(acceptanceStatus)) {
				newAcceptanceStatusSet.add(equivStatusString);
			}else {
				newAcceptanceStatusSet.add(acceptanceStatus);
			}
		}

		this.statusSet = newStatusSet;
		this.deltaMap = newDeltaMap;
		this.startStatus = newStartStatus;
		this.acceptanceStatusSet = newAcceptanceStatusSet;
	}

	/**
	 * 全ての等価な状態の集合を縮小する関数。
	 * @param equivStatusSetSet 等価な状態の集合の集合
	 */
	private void shrinkAllEquivStatus(Set<Set<String>> equivStatusSetSet) {
		for(Iterator<Set<String>> equivStatusSetIterator = equivStatusSetSet.iterator(); equivStatusSetIterator.hasNext(); ) {
			Set<String> equivStatusSet = equivStatusSetIterator.next();
			if(equivStatusSet.size() > 1) {
				shrinkEquivStatus(equivStatusSet);
			}
		}
	}
}