非決定性有限オートマトン
M の状態遷移図は以下のようになる。
M はふたつのDFAの和集合のようになっている。ひとつのDFAは状態 {S2, S1} を持ち、もうひとつは状態 {S3, S4} を持つ。
最終状態 S1 にあるとき、それまでの入力文字列に偶数個の 0 が含まれていたことを意味し、状態 S2 にあるときは奇数個であることを意味する。1 が入力されたとき、上のオートマトンの状態は変化しない。Mが受理されたとき、入力文字列に偶数個の 0 が含まれていた事がわかる。
最終状態 S3 にあるとき、それまでの入力文字列に偶数個の 1 が含まれていたことを意味し、状態 S4 にあるときは奇数個であることを意味する。0 が入力されたとき、下のオートマトンの状態は変化しない。Mが受理されたとき、入力文字列に偶数個の 1 が含まれていた事がわかる。
Mの言語は以下の正規表現で記述される正規言語である。
( 1 ∗ ( 01 ∗ 01 ∗ ) ∗ ) ∪ ( 0 ∗ ( 10 ∗ 10 ∗ ) ∗ ) {\displaystyle (1^{*}(01^{*}01^{*})^{*})\cup (0^{*}(10^{*}10^{*})^{*})}