ブラウザよりも高速アクセス！
18 関係: 形式言語、形式言語の階層、形式文法、チューリングマシン、チョムスキー階層、プッシュダウン・オートマトン、オートマタ、セル・オートマトン、線形拘束オートマトン、非決定性チューリングマシン、非決定性有限オートマトン、計算可能関数、計算モデル、計算理論、抽象機械、正規表現、決定性有限オートマトン、有限オートマトン。
形式言語
形式言語（けいしきげんご、formal language）は、その文法（構文、統語論）が、場合によっては意味（意味論）も、形式的に与えられている（形式体系を参照）言語である。形式的でないために、しばしば曖昧さが曖昧なまま残されたり、話者集団という不特定多数によってうつろいゆくような自然言語のそれに対して、一部の人工言語や、いわゆる機械可読な（機械可読目録を参照）ドキュメント類などは形式言語である。この記事では形式的な統語論すなわち構文の形式的な定義と形式文法について述べる。形式的な意味論については形式意味論の記事を参照。.
新しい！!: オートマトンと形式言語 · 続きを見る »
形式言語の階層
形式言語の階層は形式言語の包含階層で、計算理論や形式言語学などにおいて研究される。計算複雑性理論の記述計算量や複雑性クラスとも密接に関係する。1956年に発表されたチョムスキー階層に始まるが、その後の（主に計算理論とその周辺分野での）研究により、一般化・細分化が進められた。また、この包含階層の一部を可算個に分ける階層も幾つか知られている。.
新しい！!: オートマトンと形式言語の階層 · 続きを見る »
形式文法
形式文法（けいしきぶんぽう、Formal Grammar）は、形式的に与えられた（形式体系を参照）文法である。「言語」をその言語における文の集合として与えるものとして、ここでは、（有限の）文字群上の有限長の文字列の（通常無限な）集合が、形式的に記述される。 形式文法にはふたつの捉えかたがある。それは「生成」と「分析」である。#チョムスキー階層の節および単独記事に詳細があるが、両者は対応するので、ある意味では同じものをそれぞれ逆の側から見たものにすぎない。 以下で「文法の規則（構文規則）の集まり」と呼んでいるのは、具体的には、句構造規則#基本モデルにあるようなものである。また終端記号と非終端記号の記事も参照のこと。.
新しい！!: オートマトンと形式文法 · 続きを見る »
チューリングマシン
チューリングマシン (Turing Machine) は計算模型のひとつで、計算機を数学的に議論するための単純化・理想化された仮想機械である。.
新しい！!: オートマトンとチューリングマシン · 続きを見る »
チョムスキー階層
チョムスキー階層（チョムスキーかいそう、Chomsky Hierarchy）は、形式言語を生成する形式文法の包含階層（「形式言語の階層」）で、「句構造文法（Phrase Structure Grammars）の階層」などとも言う。1956年にノーム・チョムスキーが発表した。.
新しい！!: オートマトンとチョムスキー階層 · 続きを見る »
プッシュダウン・オートマトン
プッシュダウン・オートマトン（Pushdown Automaton）は、オートマトンの一種であり、文脈自由言語を認識する抽象機械である。 ある意味では、プッシュダウン・オートマトンは有限オートマトンと無限の容量のスタックを組み合せたシステムである。.
新しい！!: オートマトンとプッシュダウン・オートマトン · 続きを見る »
オートマタ
ートマタ（Automata 複数形）、オートマトン（Automaton 単数形）は、主に12世紀から19世紀にかけてヨーロッパ等で作られた機械人形ないしは自動人形のこと。 本項で述べる人形は、日本の伝統的な機械仕掛けの人形をからくりと呼ぶのに倣うと、いわゆる「西洋からくり人形」に該当する。.
新しい！!: オートマトンとオートマタ · 続きを見る »
セル・オートマトン
Daniel Dennett (1995), ''Darwin's Dangerous Idea'', Penguin Books, London, ISBN 978-0-14-016734-4, ISBN 0-14-016734-X セル・オートマトン（cellular automaton、略称：CA）とは、格子状のセルと単純な規則による、離散的計算モデルである。計算可能性理論、数学、物理学、複雑適応系、数理生物学、微小構造モデリングなどの研究で利用される。非常に単純化されたモデルであるが、生命現象、結晶の成長、乱流といった複雑な自然現象を模した、驚くほどに豊かな結果を与えてくれる。 正確な発音に近いセルラ・オートマトンとも呼ばれることがある。セルは「細胞」「小部屋」、セルラは「細胞状の」、オートマトンは「からくり」「自動機械」を意味する。他に「セル空間」「埋め尽くしオートマトン」「homogeneous structure」「tessellation structure」「iterative array」といった呼称もある。 有限種類の（多くは2から数十種類の）状態を持つセル（細胞のような単位）によってセル・オートマトンは構成され、離散的な時間で個々のセルの状態が変化する。その変化は、ある時刻 t においてのセルの状態、および近傍のセルの内部状態によって、次の時刻t+1 、すなわち新たな「ジェネレーション」（世代）での各セルの状態が決定される。初期状態（時刻 t.
新しい！!: オートマトンとセル・オートマトン · 続きを見る »
線形拘束オートマトン
線形拘束オートマトン（せんけいこうそくオートマトン、Linear Bounded Automaton）は、制限されたチューリングマシンである。LBA と略記される。有限種類の文字を保持できるテープとそのテープの読み書きができるヘッドを持ち、有限数の状態を持つ。チューリングマシンと異なるのは LBA のテープ長が有限であることで、その長さはテープ上の初期入力文字列の長さに比例する（つまり一次関数である）。この制限により LBA はある意味ではチューリングマシンよりも実在のコンピュータの正確なモデルと言える。 線形拘束オートマトンは文脈依存言語を受容する。そのクラスの言語の文法で制限されていることは、ある文字列から短い別の文字列へのマッピングを持たないことである。したがって、文脈依存言語によって生成される文字列は、それ自身より長い文型を内包することができない。線形拘束オートマトンと文脈依存言語は一対一の対応関係にあるので、本来の文字列が書かれたテープの長さがあれば、そのオートマトンに理解できる文字列には必要十分である。.
新しい！!: オートマトンと線形拘束オートマトン · 続きを見る »
非決定性チューリングマシン
非決定性チューリング機械（ひけっていせいチューリングきかい、Non-deterministic Turing machine, NTM）は、理論計算機科学において、非決定性有限オートマトンのように働く制御機構を持つチューリング機械である。.
新しい！!: オートマトンと非決定性チューリングマシン · 続きを見る »
非決定性有限オートマトン
非決定性有限オートマトン（）または非決定性有限状態機械（）は、有限オートマトンの一種であり、ある状態と入力があったとき、次の遷移先が一意に決定しないことがあるものである。NFAと略記される。.
新しい！!: オートマトンと非決定性有限オートマトン · 続きを見る »
計算可能関数
計算可能関数（けいさんかのうかんすう、Computable function）は、計算可能性理論研究の基本的な目的で、直観的には、アルゴリズムによって結果の値が得られる関数のことである。計算可能関数は、チューリングマシンやレジスタマシンといった具体的な計算モデルを参照せずに、計算可能性を論じるのに使われる。しかし、その定義には特定の計算モデルを参照する必要がある。 計算可能関数の正確な定義が与えられる以前から、数学者は effectively computable（実効的に計算可能）という言い回しをよく使っていた。現在では、その概念が計算可能関数となっている。effective（実効的）であってもefficient（効率的）に計算できるということは導かない。実際、計算可能関数には非効率な場合もある。計算複雑性理論は、そのような関数の計算効率を研究している。 チャーチ＝チューリングのテーゼによれば、計算可能関数は、任意にいくらでも拡大できる記憶装置を持った計算機械を使い（いくら長くても良いが）有限の時間で計算が必ず終了する関数である。アルゴリズムのある関数は全て計算可能である。 ブラムの公理を使って、計算可能関数の集合について抽象的な計算複雑性を定義できる。計算複雑性理論では、計算可能関数の複雑性を特定する問題を函数問題と呼ぶ。.
新しい！!: オートマトンと計算可能関数 · 続きを見る »
計算モデル
計算モデル（model of computation）とは、人工的な計算機を含め、計算・推論・証明といった行為を理論的・抽象的に考察するための数理モデルのことである。計算模型とも。 また、抽象機械（abstract machine）と言った場合、主にオートマトン理論での計算システムの理論的モデルを意味する。 計算過程の抽象化は計算機科学と計算機工学で一般に使われる手法である。 計算モデルのもうひとつの定義として、複雑系をコンピュータシミュレーションで研究する際に、自然現象を計算できるようにモデル化したものも意味する。 計算理論において、抽象機械はアルゴリズムの計算可能性や計算複雑性に関する思考実験で使われることが多い。 典型的な抽象機械はチューリングマシンに代表される、入力と出力を定義し、入力から出力を生成するための可能な操作を定義したものである。 より現実の計算機に近づけた機械の定義には命令セット、レジスタ、メモリモデルなども含まれる。現在の一般的なコンピュータ（要するにいわゆるノイマン型）を抽象化した計算モデルとしてはRAMモデルがある。これはインデックス付きのメモリに対してランダムにアクセス可能な計算モデルである。キャッシュメモリが一般化し、そのヒット率が性能に与える影響が大きくなってくると、メモリの階層を前提とした計算モデルが重要となってきた。 ハードウェアとして実装されていない（実装する予定のない）マイクロプロセッサの設計も一種の抽象機械である。特にインタプリタの形式でソフトウェアとして実装されている抽象機械を仮想機械と呼ぶ。 抽象機械を使用することで、実際にシステムを組み立てることなく時間、メモリ使用量など特定の操作の実行に要するリソースを計算で求めることが可能である。.
新しい！!: オートマトンと計算モデル · 続きを見る »
計算理論
計算理論（けいさんりろん、theory of computation）は、理論計算機科学と数学の一部で、計算模型やアルゴリズムを理論的にあつかう学問である。計算複雑性理論、計算可能性理論を含む。ここでいう計算 (computation) とは、数学的に表現できる、あらゆる種類の情報処理のこと。 計算を厳密に研究するため、計算機科学では計算模型と呼ばれるコンピュータの数学的抽象化を行う。その手法はいくつかあるが、最も有名なものはチューリングマシンである。チューリングマシンは、言ってみれば無限のメモリを持つコンピュータであるが、一度にアクセスできるメモリ範囲は非常に限られている。チューリングマシンは十分な計算能力を持つモデルでありながら、単純で定式化しやすく、様々な証明に使い易いため、計算機科学者がよく利用する。無限のメモリというのは非現実的な特徴と思われるかもしれないが、より適切な表現を使うならば「無制限」のメモリであって、読み書きしようとした時にそれができればよく、それに対応する「無限な実体」とでも言うべきものが必要なわけではない。「チューリングマシンで、ある問題が解ける」とは必ず有限のステップで計算が終了することを意味し、よってそれに必要なメモリの量は有限である。よって、チューリングマシンで解くことが出来る問題は、現実のコンピュータであっても必要なだけのメモリがあれば解くことが出来る。.
新しい！!: オートマトンと計算理論 · 続きを見る »
抽象機械
抽象機械（抽象コンピュータとも呼ばれる）は、オートマトンで利用される、コンピュータハードウェアやソフトウェアシステムの理論上モデルである。 計算処理の抽象化は、計算機科学と計算機工学の両方の分野で行われ、通常は離散時間パラダイムを仮定している。.
新しい！!: オートマトンと抽象機械 · 続きを見る »
正規表現
正規表現（せいきひょうげん、regular expression）とは、文字列の集合を一つの文字列で表現する方法の一つである。正則表現（せいそくひょうげん）とも呼ばれ、形式言語理論の分野では比較的こちらの訳語の方が使われる。まれに正規式と呼ばれることもある。 もともと正規表現は形式言語理論において正規言語を表すための手段として導入された。形式言語理論では、形式言語が正規言語であることと正規表現によって表せることは同値である。 その後正規表現はテキストエディタ、ワードプロセッサなどのアプリケーションで（ないし、そもそもそれ以前に単機能の文字列探索ツールの）、マッチさせるべき対象を表すために使用されるようになり、表せるパターンの種類を増やすために本来の正規表現にはないさまざまな記法が新たに付け加えられた。このような拡張された正規表現には正規言語ではない文字列も表せるものも多く、ゆえに正規表現という名前は実態に即していない面もあるが、伝統的に正規表現と呼ばれ続けている。 この記事では主にこのような正規表現を用いたパターンマッチングについて説明している。以下、誤解のない限り、アプリケーションやプログラミングにおいて正規表現を用いた文字列のパターンマッチングを行う機能のことを、単に正規表現という。 ほとんどのプログラミング言語では、ライブラリによって正規表現を使うことができる他、一部の言語では正規表現のリテラルもある。「正規表現によるマッチ」を意味する（専用の）演算子がある言語なども一部ある。具体例として、grep、AWK、sed、Perl、Tcl、lexなどがある。 それぞれの言語やアプリケーションで細部の仕様が異なっている、といったように思われることも多いが（また、古い実装では実際にそういうことも多いが）、近年は同じライブラリを使っていれば同じということも多い。またPOSIXなど標準もある。.
新しい！!: オートマトンと正規表現 · 続きを見る »
決定性有限オートマトン
決定性有限オートマトン（けっていせいゆうげんオートマトン、Deterministic Finite Automaton）または決定性有限状態機械（けっていせいゆうげんじょうたいきかい、Deterministic Finite State Machine）は、状態と入力によって次に遷移すべき状態が一意に定まる有限オートマトンである。DFA と略記される。 DFAは入力文字列を受け付ける。各入力文字について、遷移関数にしたがって新たな状態に遷移する。最後に入力文字を受け付けたとき、受理状態であれば入力文字列は受理された、そうでなければ入力文字列は拒否されたと判断される。 非決定性有限オートマトンは、決定性有限オートマトンと同じように正規集合を認識でき、必ず決定性オートマトンに変換できる。.
新しい！!: オートマトンと決定性有限オートマトン · 続きを見る »
有限オートマトン
有限オートマトン（finite automaton)または有限状態機械（finite state machine, FSM）とは、有限個の状態と遷移と動作の組み合わせからなる数学的に抽象化された「ふるまいのモデル」である。デジタル回路やプログラムの設計で使われることがあり、ある一連の状態をとったときどのように論理が流れるかを調べることができる。有限個の「状態」のうち1つの状態をとる。ある時点では1つの状態しかとらず、それをその時点の「現在状態」と呼ぶ。何らかのイベントや条件によってある状態から別の状態へと移行し、それを「遷移」と呼ぶ。それぞれの現在状態から遷移しうる状態と、遷移のきっかけとなる条件を列挙することで定義される。 有限オートマトンは様々な問題に応用でき、半導体設計の自動化、通信プロトコル設計、構文解析などの工学面での応用がある。生物学や人工知能研究では状態機械（群）を使って神経系をモデル化し、言語学では自然言語の文法をモデル化したりする。.
新しい！!: オートマトンと有限オートマトン · 続きを見る »
