[A]例1.56

いくつかの段階を経ることで、正規表現 (ab∪a)* を NFAに変換しよう．図 1.57に示す遷移図からもわかるように，表現に対応する NFAを得るまで，最も小さな部分的表現から，より大きな部分的表現へと構成していく．一般的に，この手順が状態数の最小な NFAを作るとは限らない．この例では，8個の状態からなる NFAを与えているが，等価な NFAの中で最も小さいものはわずか 2個の状態しかもたない．読者は，それを見つけられるだろうか?

DOT言語による答案と、それを Graphvizに通して得た状態遷移図

digraph NFA {
	rankdir=LR

	/* Q:set of states */
	q1  [shape=circle]
	q2  [shape=circle]

	/* Σ:alphabet */
	// a
	// b

	/* δ:transition function */
	q1 -> q1 [label=a]
	q1 -> q2 [label=a]
	q2 -> q1 [label=b]

	/* q0:start state */
	q0  [shape=point]
	q0 -> q1

	/* F:set of accept states */
	q1 [shape=doublecircle];
}

>dot "例1.56.dot" -Tgif -o"例1.56.gif"