ε動作

順序機械、有限オートマトン、死状態と推移不許可、有限オートマトンの決定性と非決定性、部分集合構成法

　普通は、有限オートマトンの状態推移は入力によって起こると考えるので、入力がないときは状態は推移しない（同じ状態にとどまる）ことになるよ。この「入力がない」ことを記号「ε」（イプシロン）で表すよ。
　さて、とはいえ、設計によっては、入力がなくても状態推移があるような機械を考えることもできるよ。この入力なしの状態推移のことをε-動作というよ。（ある状態からε-動作だけで到達可能な状態の集合を、その状態のε-閉包というよ。）
　ある状態にε-動作があるときは、その状態への入力をすることが、ε-動作後の状態への入力をすることになることもあるし、入力による状態推移後にε-動作によって別の状態に推移することもあるよ。
　たとえば状態Aから状態Bへのε-動作が定義されているときには、状態Aで入力1があるということを、状態Bで入力1があるということと動作上同じに捉えることができるよ。
　このようなε-動作をもつ非決定性有限オートマトンに対して、それと等価でありつつ、ε-動作を除去した非決定性有限オートマトンを作ることができるよ。やり方は簡単で、要するにε-動作を介して到達可能な状態に、ε-動作なしで（つまり何らかの入力で）到達できるように状態推移関数を書き直してやればいいよ。
　たとえば状態Aから状態Bにεで、状態Bから状態Cに入力1で推移するようになっている場合は、状態Aのときに1を入力してもε-動作を介して状態Bに入力1があったのと同じということで状態Cに推移できるわけだから、これを直接、状態Aに入力1があると次の状態はC、というふうに書けばいいよ。
　あと、最終状態は基本的に同じでいいけど、もとの機械が、初期状態からε-動作だけで最終状態に到達できるようになっているとき（つまり初期状態のε-閉包に最終状態が含まれているとき）は、これは要するに何もしないでも受理ということだから、ε-動作を除去するときは、これにあわせて初期状態も最終状態とする必要があるよ。