【有限オートマトンとは】種類・例題

有限オートマトンとは?種類・例題などについてまとめました。

有限オートマトンは、入力値と入力されたときの状態で出力値が決まる順序機械に言語を識別するアルゴリズムを与えた数学的モデルです。

【例題】有限オートマトン

● S1状態から始まる。
● S1状態で0を出力した時はS3へ、1を出力した時はS2へ状態遷移する。
● S2状態で0を出力した時はS2を維持、1を出力した時はS1へ状態遷移する。
● S3状態で0を出力した時はS2へ状態遷移し、1を出力した時はS3を維持する。
● 入力列はS3で受理されます。

例えば、「1011」「1100」「1110」はS3が受領不可能です。
「1101」はS3が受領可能です。