世界大百科事典（旧版）内の有限オートマトンの言及
【オートマトン】より
…ここで扱われている計算モデルは，初期のオートマトンの正統な末裔といえる。
[有限オートマトン]
オートマトンの中で最も単純なモデルが有限オートマトンである。有限オートマトンを理解するために，簡単なからくり人形を思い浮かべてみよう。…
【形式言語】より
…右および左線形文法を合わせて正規文法regular grammar，あるいは3型文法といい，これによって生成される言語を正規言語，あるいは3型言語という。この型の言語の構造は最も単純で，有限オートマトンによって識別される。自然言語では，単語の水準の記号系列がこの構造をもつ。…
【チューリング機械】より
…すなわち，時刻tでMが内部状態q(t)にあり，読んでいる桝目の記号がs(t)のとき，時刻t＋1では状態f(q(t)，s(t))に入り，その桝目にs(t)の代りにg(q(t)，s(t))を書き込み，h(q(t)，s(t))＝Lならヘッドを1桝だけ左へ，h(q(t)，s(t))＝Rなら右へ動かす。 一般に機械Mの動作は(qi,sj,f(qi,sj)，g(qi,sj)，h(qi,sj))なる“5文字組”の集合で定義される(このような機械を有限オートマトンという)。f(qi,sj)の定義されていない(qi,sj)の状況に到着したときにチューリング機械は“停止する”と定義しておく。…
※「有限オートマトン」について言及している用語解説の一部を掲載しています。
出典｜株式会社平凡社「世界大百科事典（旧版）」
Sponserd by 