プッシュダウン・オートマトンとは?

Mazii

Trải nghiệm ứng dụng Mazii

Tra cứu

Từ vựng Hán tự Mẫu câu Ngữ pháp

Nhật - Nhật

Kết quả tra cứu tiếng Nhât của từ プッシュダウン・オートマトン

プッシュダウン・オートマトン

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

Từ điển Nhật - Nhật

Các từ liên quan tới プッシュダウン・オートマトン

オートマトン

〖automaton〗

リチャード・スターンズ

for Pushdown Machines, Information and Control 11(3): 323-340 (1967). 決定性プッシュダウン・オートマトンを扱った論文。 P. M. Lewis II, R. E. Stearns: Syntax-Directed Transduction

スタックマシン

（0の並びの後に同じ個数の1が並ぶ言語）のような単純な言語も認識できない。1-スタックマシンの計算能力は、有限オートマトンよりも高いが、決定性プッシュダウン・オートマトンよりも低い。一方、複数のスタックを持つスタックマシンはチューリングマシンと等価である。例えば、2-スタックマシンでは、チューリ

線形拘束オートマトン

線形拘束オートマトン（せんけいこうそくオートマトン、Linear Bounded Automaton）は、制限されたチューリングマシンである。LBA と略記される。有限種類の文字を保持できるテープとそのテープの読み書きができるヘッドを持ち、有限数の状態を持つ。チューリングマシンと異なるのは LBA

デイナ・スコット

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

セル・オートマトン

をとる外部総和型のセル・オートマトンの例である。同じく外部総和型でムーア近傍だが、規則をライフゲームとは変えたセル・オートマトンを欧米では "life-like" と呼ぶ。 CAの概念は様々な拡張が可能である。例えば、矩形の格子ではなく別の多角形を使うという拡張がある。例えば六角形

有限オートマトン

このタイプの有限オートマトンは入力を受容（accept）したり、理解（recognize）して、外界に結果を知らせるために状態（state）を使用する。つまり、最終的に受容状態になったかどうかで「はい」または「いいえ」のいずれかを出力として返す。FSMの全状態は受容状態かそうでないかのいずれかである。全入力

Malbolge

Malbolgeプログラムを書くことができるとし、例として入力された文字を出力するプログラムを示した。 OlmsteadはMalbolgeが線形拘束オートマトンであると考えていた。無限ループが初めて発表されるまでに何年も要しており、Malbolgeにおける実用的なループのインプリメント可能性に関し、さらに興味深い議論がある。[要出典]