有限オートマトン（ゆうげんオートマトン、英: finite automaton）または有限状態機械（ゆうげんじょうたいきかい、（）英: finite state machine, FSM）とは、有限個の状態と遷移と動作の組み合わせからなる数学的に抽象化された「ふるまいのモデル」である。デジタル回路...

オートマトン (単数形: 英: automaton [ɔːˈtɑməˌtɑn], 複数形: オートマタ（automata [ɔːˈtɑmətə]）) とは、自動人形などとも呼ばれる「オートマタ」と同じ語であるが、計算理論において、計算モデルに関して有限オートマトン...

決定性有限オートマトン（けっていせいゆうげんオートマトン、英: Deterministic Finite Automaton）または決定性有限状態機械（けっていせいゆうげんじょうたいきかい、英: Deterministic Finite State Machine）は、状態と入力によって次に遷移すべ...

structure」「tessellation structure」「iterative array」といった呼称もある。 有限種類の（多くは2から数十種類の）状態を持つセル（細胞のような単位）によってセル・オートマトンは構成され、離散的な時間で個々のセルの状態が変化する。その変化は、ある時刻 t...

有限オートマトン がある。 また、ソフトウェアに相当するものとして、以下がある。 テープに読み書きされる有限個の種類の記号 最初から（初期状態において）テープにあらかじめ書かれている記号列 有限オートマトンの状態遷移規則群。詳細は次で述べる この有限オートマトン...

非決定性有限オートマトン（ひけっていせいゆうげんオートマトン、英: nondeterministic finite automaton、NFA）または非決定性有限状態機械（ひけっていせいゆうげんじょうたいきかい、英: nondeterministic finite state...

プッシュダウン・オートマトン（英: pushdown automaton, PDA）は、オートマトンの一種であり、文脈自由言語を認識する抽象機械である。 ある意味では、プッシュダウン・オートマトンは有限オートマトンと無限の容量のスタックを組み合せたシステムである。 プッシュダウンオートマトンは通常の有限オートマトンとは以下の二点で異なる。...

オートマトン(の)理論」と呼ぶことがある（この文脈では「オートマトン」とは、チューリングマシンより弱い（制限された）機械の総称である）。 正規表現は文字列パターンを指定するのによく使われる。また、それと等価な有限オートマトン...

書かれている。値が書かれていないノードはキー文字列の途中までにしか対応していない。各英単語には整数の値が対応している。 トライ木は一種の決定性有限オートマトンと見ることもできるが、エッジ（枝）に対応する記号（文字）はその順序が暗黙のうちに決定される（辞書順など）。...

"Finite Automata and Their Decision Problems"（有限状態機械とその決定性問題）を書いた。間もなく非決定性有限オートマトンを活用して、クリーネの「有限状態機械は正確に正規言語を受理する」という結論を再証明することができた。...

る。利用可能な計算モデルはいくつか存在する。以下に代表例を挙げる。 決定性有限状態機械 決定性有限オートマトン（DFA）、あるいは単に有限状態機械とも呼ぶ。単純な計算モデルである。現在、実際に使われているコンピュータは、有限状態機械としてモデル化できる。この機械は状態の集合を持ち、入力列によって働...

状態遷移図（じょうたいせんいず、State Transition Diagram）は、有限オートマトンなどの状態機械について、その各状態を頂点とし、状態から状態への各遷移を辺としたグラフ構造に注目して、グラフィカルに表現した図である。他の表現手法として状態遷移表などがある。...

正規言語（せいきげんご）または正則言語（せいそくげんご）は、以下に示す性質（いずれも等価）を満たす形式言語である。 決定性有限オートマトンによって受理可能 非決定性有限オートマトンによって受理可能 正規表現で記述可能 正規文法から生成可能 読みとり専用チューリングマシンで受理可能 文字セット Σ...

セッサの演算装置やレジスタの動作や、記憶装置の読み書き、入出力などを制御する装置である。 この装置の出力は他の装置の活動を制御する。制御装置は有限オートマトンでモデル化される。理論的にはシーケンス制御がおこなうことと同じだが、一般にはシーケンス制御の語はプロセッサの制御を指しては使われていない。...

にこの言葉を使う。特に、植物群集を中心にした遷移は、生態系の発達にも関わって重要である。 オートマトン理論として知られている情報工学の一分野では、遷移とはシステムの状態が変化することを意味する。有限オートマトンは矢印付きの弧でその遷移を表す一方、ペトリネットは特別なノードの要素として表す。状態遷移表、状態遷移図も参照されたい。...

FO[S,<] と等価である。また、クリーネスターのない正規表現や loop complexity が 0 であるような決定性有限オートマトンも LTL と等価である。 有限状態検証における時相論理 計算木論理 (CTL) CTL* (英語版) インターバル時相論理 (ITL) A presentation...

{\displaystyle \alpha } が変数であるとき、 ∀ α ϕ {\displaystyle \forall \alpha \phi } 、 ∃ α ϕ {\displaystyle \exists \alpha \phi } も論理式である。 形式体系 形式言語 形式文法 有限オートマトン...

間不変系（英語版）の基本モデルである。また偏微分方程式論では、半群は空間発展的かつ時間非依存な任意の方程式に対応している。有限半群論は1950年代以降、有限半群と有限オートマトンとの間の自然な関連性から、理論計算機科学の分野で特に重要となっている。確率論では半群はマルコフ過程に関連付けられる (Feller...

以下の二つの事実が示すように、正規列と有限オートマトンとの間にはより深い関係がある。 有限状態ギャンブラー（finite-state gambler または finite-state martingale、以下 FSG）とは、有限アルファベット Σ 上の有限オートマトンの状態に応じて文字たち（Σ...

形式言語とオートマトンの理論において、アルファベット (英: alphabet) または字母とは、文字や数字などといったような「記号」の有限の集合のこと。有限の文字列は、アルファベットからなる文字の有限の並びである。特に、{0, 1}からなるアルファベットはバイナリアルファベットと呼ばれる。また、二進列...

→ ϵ {\displaystyle S\rightarrow \epsilon } という規則が存在しても良い。この文法で生成される言語群は有限オートマトンで判定可能である。さらにこのタイプの形式言語は正規表現として使用されている。正規言語は検索パターンの定義やプログラミング言語の字句構造に一般的に使われている。...

という論文を発表し、非決定性有限オートマトンのアイデアを明らかにした。これが計算複雑性理論の基礎概念となったことから、ラビンと共にチューリング賞を受賞した。 彼の業績はオートマトン理論、公理的集合論、プログラミング言語の意味論、言語哲学等、多岐にわたっており、1959年にマイケル・ラビンと共同で発表したオートマトン理論に関する研究...

非決定性チューリング機械（ひけっていせいチューリングきかい、英: Non-deterministic Turing machine, NTM）は、理論計算機科学において、非決定性有限オートマトンのように働く制御機構を持つチューリング機械である。 通常の（決定性）チューリング機械（DTM）の遷移機構は、現在状態とテープ上のヘッドの現在位...

Grammar）は、形式的に与えられた（形式体系を参照）文法である。「言語」をその言語における文の集合として与えるものとして、ここでは、（有限の）文字群上の有限長の文字列の（通常無限な）集合が、形式的に記述される。 形式文法にはふたつの捉えかたがある。それは「生成」と「分析」である。#チョムスキー...

パターンは単一のオブジェクトに対して働くためである。 memento パターンの古典的な例として、擬似乱数発生器や、有限オートマトンの状態などがある。 以下の Java プログラムは、 Memento パターンを "undo" に使った場合を示す。 import java.util...

に対する対応が大変だった。そのため、自動の「オートマトン」と呼ばれる自動対応装置を導入し.ukはさらに急成長した。 ac.uk-高等教育と研究施設(アカデミック) co.uk-コマーシャル/一般 gov.uk-中央政府と地方政府 ltd. uk-非公開有限責任会社 me.uk-個人 mod.uk-イギリス国防省とHM...

– ノート] また、モノイドの性質も持つ。 カラーペトリネット（英語版） 並行計算 性能評価 通信プロトコル バイオインフォマティクス ペトリネットの解析 有限オートマトン ペトリネット言語 アクターモデル、プロセス計算 表示的意味論 アクティビティ図 YAWL BPEL グラフ理論 オープンペトリネット...

に遷移する可能性がある。以上のような場合があるため、この有限オートマトンは非決定性であると言える。 状態遷移表から状態遷移図を描くことができる。その簡単な手順は以下のようになる。 表に出てくる状態に対応した円を描く。 各状態について、対応する行を見て、遷移先の状態（群）への矢印を描く。そのオートマトンがNFAの場合、一種類の入力で複数の矢印が存在する場合がある。...

ュータ上で実行できるクワイン・マクラスキー法の登場であった。これにより選言標準形や連言標準形で2段の論理ゲートを最小化する手法が確立した。その他の初期の論理最小化の研究として、有限オートマトンの符号化と状態最小化があった。論理合成の主な応用としてデジタルコンピュータ設計がある。初期の論理合成自動化については、IBM...

ラビンオートマトン（Rabin Automaton）は、無限長の文字列を扱う有限オートマトンの一種。その形式は A = ( Q ,   Σ ,   q 0 ,   δ ,   Ω ) {\displaystyle {\mathcal {A}}=(Q,~\Sigma ,~q_{0},~\delta ...

のようにして構成的に定めることもできる。 タプルは様々な数学概念を定義するためにも利用される。 例えば、有限オートマトンは、入力アルファベットの有限集合 Σ, 状態の有限集合 S, 初期状態 s0 ∈ S, 遷移関数 δ : Σ × S → S, 受理状態の有限集合 F ⊆ S の 5 つ組 (quintuple, 5-tuple)...