適用可能な遷移規則が複数存在し得る。方が強力なモデルに見えるが、両者で受理可能な言語の集合は一致しており計算能力に差異は無い。行うのは、入力文字列が遷移規則で定義された文字列の集合に属するか、という計算である。このような文字列の集合は言語と呼ばれる。始まる文字列を全て含む言語」を認識するといえる。受理可能な言語全体の集合というものを定義できる。受理可能な言語の集合は正規表現で記述できる言語の集合と一致することが知られており、正規言語と呼ばれる。入力文字列が正規言語であるかしか答えられない。四則演算を行うことが不可能。正規言語に属さない形式言語に関しても受理可能かを判断することができない。表現することは不可能。