ロゴ
ユニオンペディア
コミュニケーション
Google Play で手に入れよう
新しい! あなたのAndroid™デバイスでユニオンペディアをダウンロードしてください!
インストール
ブラウザよりも高速アクセス!
 

非決定性有限オートマトン

索引 非決定性有限オートマトン

非決定性有限オートマトン()または非決定性有限状態機械()は、有限オートマトンの一種であり、ある状態と入力があったとき、次の遷移先が一意に決定しないことがあるものである。NFAと略記される。.

14 関係: 形式言語データ構造アルファベット (計算機科学)オブジェクト指向冪集合状態遷移図状態遷移表配列正規表現正規言語決定性有限オートマトン指数関数有限オートマトン有限集合

形式言語

形式言語(けいしきげんご、formal language)は、その文法(構文、統語論)が、場合によっては意味(意味論)も、形式的に与えられている(形式体系を参照)言語である。形式的でないために、しばしば曖昧さが曖昧なまま残されたり、話者集団という不特定多数によってうつろいゆくような自然言語のそれに対して、一部の人工言語や、いわゆる機械可読な(機械可読目録を参照)ドキュメント類などは形式言語である。この記事では形式的な統語論すなわち構文の形式的な定義と形式文法について述べる。形式的な意味論については形式意味論の記事を参照。.

新しい!!: 非決定性有限オートマトンと形式言語 · 続きを見る »

データ構造

データ構造(データこうぞう、data structure)は、計算機科学において、データの集まりをコンピュータの中で効果的に扱うため、一定の形式に系統立てて格納するときの形式のことである。 ソフトウェア開発において、データ構造についてどのような設計を行うかは、プログラム(アルゴリズム)の効率に大きく影響する。そのため、さまざまなデータ構造が考え出されている。 多くのプログラムの設計において、データ構造の選択は主要な問題である。これは大規模システムの構築において、実装の困難さや質、最終的なパフォーマンスはベストのデータ構造を選択したかどうかに大きく依存してきたという経験の結果である。多くの場合、データ構造が決まれば、利用するアルゴリズムは比較的自明に決まる。しかし場合によっては、順番が逆になる。つまり、与えられた仕事をこなす最適なアルゴリズムを使うために、そのアルゴリズムが前提としている特定のデータ構造が選択される。いずれにしても適切なデータ構造の選択は極めて重要である。 この洞察は、多くの定式化された設計手法やプログラミング言語において、データ構造がアルゴリズムよりもキーとなる構成要素となっていることに現れている。大半の言語は異なるアプリケーションにおいてデータ構造を安全に再利用できるよう、実装の詳細をインターフェイスの背後に隠蔽するような、モジュール化のしくみを備えている。C++やJavaといったオブジェクト指向プログラミング言語はクラスをこの目的に用いている。 データ構造は専門的なプログラミングにとって非常に重要なので、C++におけるSTLや、Java API、および.NET Frameworkのようなプログラミング言語の標準ライブラリや環境において多くのデータ構造がサポートされている。 データ構造が実装を表すのかインターフェースを表すのかについてはいくらか議論がある。どのように見えるかは相対的な問題なのかもしれない。データ構造は2つの関数の間にあるインターフェイスとして見ることもできるし、データ型に基づいて構成されたストレージにアクセスする方法を実装したものとして見ることもできる。.

新しい!!: 非決定性有限オートマトンとデータ構造 · 続きを見る »

アルファベット (計算機科学)

形式言語とオートマトンの理論において、アルファベット (英: alphabet) または字母とは、文字や数字などといったような「記号」の有限の集合のこと。有限の文字列は、アルファベットからなる文字の有限の並びである。特に、からなるアルファベットはバイナリアルファベットと呼ばれる。また、二進列 (binary string)は、バイナリアルファベットの並びである。また、うまく処理することで、無限の文字の並びも考えることが可能である。 アルファベットΣが与えられたとき、Σ*はアルファベットΣからなる有限の文字列全てを意味する。ここでの*はクリーネ閉包を意味する演算子である。また、\Sigma^\infty (or occasionally, \Sigma^\N or \Sigma^\omega)は、アルファベットΣからなる無限の文字列全てを意味する。 例えばバイナリアルファベットからはのような文字列が生成できる(εは空文字列を意味する)。.

新しい!!: 非決定性有限オートマトンとアルファベット (計算機科学) · 続きを見る »

オブジェクト指向

ブジェクト指向(オブジェクトしこう)とは、オブジェクト同士の相互作用として、システムの振る舞いをとらえる考え方である。英語の object-oriented (直訳は、「対象物志向の」「目的重視の」という意味の形容詞) の日本語訳である。 オブジェクト指向の枠組みが持つ道具立ては、一般的で強力な記述能力を持つ。複雑なシステム記述、巨大なライブラリ(特に部品間で緊密で複雑な相互関係を持つもの)の記述においては、オブジェクト指向の考え方は必須である。.

新しい!!: 非決定性有限オートマトンとオブジェクト指向 · 続きを見る »

冪集合

冪集合(べきしゅうごう、power set)とは、数学において、与えられた集合から、その部分集合の全体として新たに作り出される集合のことである。べきは冪乗の冪(べき)と同じもので、冪集合と書くのが正確だが、一部分をとった略字として巾集合とも書かれる。 集合と呼ぶべき対象を公理的に構成的に与える公理的集合論では、集合から作った冪集合が集合と呼ばれるべきもののうちにあることを公理の一つ(冪集合公理)としてしばしば提示する。.

新しい!!: 非決定性有限オートマトンと冪集合 · 続きを見る »

状態遷移図

態遷移図(じょうたいせんいず、State Transition Diagram)は、有限オートマトンなどの状態機械について、その各状態を頂点とし、状態から状態への各遷移を辺としたグラフ構造に注目して、グラフィカルに表現した図である。他の表現手法として状態遷移表などがある。 状態遷移図にはいくつかの異なる形式のものがある。対象の性質や用途などによって使い分けることもある。.

新しい!!: 非決定性有限オートマトンと状態遷移図 · 続きを見る »

状態遷移表

態遷移表(じょうたいせんいひょう、State Transition Table)は、状態機械類(の遷移関数 T(scurrent, e).

新しい!!: 非決定性有限オートマトンと状態遷移表 · 続きを見る »

配列

この記事では、コンピュータ・プログラムにおいて配列(はいれつ、array)と呼ばれているデータ構造およびデータ型について説明する。計算科学方面ではベクトルという場合もある。また、リストも参照。一般に、添え字で個々の要素を区別する。.

新しい!!: 非決定性有限オートマトンと配列 · 続きを見る »

正規表現

正規表現(せいきひょうげん、regular expression)とは、文字列の集合を一つの文字列で表現する方法の一つである。正則表現(せいそくひょうげん)とも呼ばれ、形式言語理論の分野では比較的こちらの訳語の方が使われる。まれに正規式と呼ばれることもある。 もともと正規表現は形式言語理論において正規言語を表すための手段として導入された。形式言語理論では、形式言語が正規言語であることと正規表現によって表せることは同値である。 その後正規表現はテキストエディタ、ワードプロセッサなどのアプリケーションで(ないし、そもそもそれ以前に単機能の文字列探索ツールの)、マッチさせるべき対象を表すために使用されるようになり、表せるパターンの種類を増やすために本来の正規表現にはないさまざまな記法が新たに付け加えられた。このような拡張された正規表現には正規言語ではない文字列も表せるものも多く、ゆえに正規表現という名前は実態に即していない面もあるが、伝統的に正規表現と呼ばれ続けている。 この記事では主にこのような正規表現を用いたパターンマッチングについて説明している。以下、誤解のない限り、アプリケーションやプログラミングにおいて正規表現を用いた文字列のパターンマッチングを行う機能のことを、単に正規表現という。 ほとんどのプログラミング言語では、ライブラリによって正規表現を使うことができる他、一部の言語では正規表現のリテラルもある。「正規表現によるマッチ」を意味する(専用の)演算子がある言語なども一部ある。具体例として、grep、AWK、sed、Perl、Tcl、lexなどがある。 それぞれの言語やアプリケーションで細部の仕様が異なっている、といったように思われることも多いが(また、古い実装では実際にそういうことも多いが)、近年は同じライブラリを使っていれば同じということも多い。またPOSIXなど標準もある。.

新しい!!: 非決定性有限オートマトンと正規表現 · 続きを見る »

正規言語

正規言語(せいきげんご)または正則言語(せいそくげんご)は、以下に示す性質(いずれも等価)を満たす形式言語である。.

新しい!!: 非決定性有限オートマトンと正規言語 · 続きを見る »

決定性有限オートマトン

決定性有限オートマトン(けっていせいゆうげんオートマトン、Deterministic Finite Automaton)または決定性有限状態機械(けっていせいゆうげんじょうたいきかい、Deterministic Finite State Machine)は、状態と入力によって次に遷移すべき状態が一意に定まる有限オートマトンである。DFA と略記される。 DFAは入力文字列を受け付ける。各入力文字について、遷移関数にしたがって新たな状態に遷移する。最後に入力文字を受け付けたとき、受理状態であれば入力文字列は受理された、そうでなければ入力文字列は拒否されたと判断される。 非決定性有限オートマトンは、決定性有限オートマトンと同じように正規集合を認識でき、必ず決定性オートマトンに変換できる。.

新しい!!: 非決定性有限オートマトンと決定性有限オートマトン · 続きを見る »

指数関数

実解析における指数関数(しすうかんすう、exponential function)は、冪における指数 を変数として、その定義域を主に実数の全体へ拡張して定義される初等超越関数の一種である。対数関数の逆関数であるため、逆対数 と呼ばれることもある。自然科学において、指数関数は量の増加度に関する数学的な記述を与えるものとして用いられる(や指数関数的減衰の項を参照)。 一般に、 かつ なる定数 に関して、(主に実数の上を亙る)変数 を へ送る関数は、「a を'''底'''とする指数函数」と呼ばれる。「指数関数」との名称は、与えられた底に関して冪指数を変数とする関数であることを示唆するものであり、冪指数を固定して底を独立変数とする冪関数とは対照的である。 しばしば、より狭義の関数を意図して単に「指数関数」と呼ぶこともある。そのような標準的な (the) 指数関数(あるいはより明示的に「自然指数関数」)はネイピア数 を底とする関数 である。これを のようにも書く。この関数は、導関数が自分自身に一致するなど、他の指数関数と比べて著しい性質を持つ。底 を他の底 に取り換えるには自然対数 を用いて、等式 を適用すればよいから、以下本項では主に自然指数関数について記述し、多くの場合「指数関数」は自然指数関数の意味で用いる。.

新しい!!: 非決定性有限オートマトンと指数関数 · 続きを見る »

有限オートマトン

有限オートマトン(finite automaton)または有限状態機械(finite state machine, FSM)とは、有限個の状態と遷移と動作の組み合わせからなる数学的に抽象化された「ふるまいのモデル」である。デジタル回路やプログラムの設計で使われることがあり、ある一連の状態をとったときどのように論理が流れるかを調べることができる。有限個の「状態」のうち1つの状態をとる。ある時点では1つの状態しかとらず、それをその時点の「現在状態」と呼ぶ。何らかのイベントや条件によってある状態から別の状態へと移行し、それを「遷移」と呼ぶ。それぞれの現在状態から遷移しうる状態と、遷移のきっかけとなる条件を列挙することで定義される。 有限オートマトンは様々な問題に応用でき、半導体設計の自動化、通信プロトコル設計、構文解析などの工学面での応用がある。生物学や人工知能研究では状態機械(群)を使って神経系をモデル化し、言語学では自然言語の文法をモデル化したりする。.

新しい!!: 非決定性有限オートマトンと有限オートマトン · 続きを見る »

有限集合

数学において、集合が有限(ゆうげん、finite)であるとは、自然数 n を用いて という形にあらわされる集合との間に全単射が存在することをいう(ただしここでは、n.

新しい!!: 非決定性有限オートマトンと有限集合 · 続きを見る »

出ていきます入ってきます
ヘイ!私たちは今、Facebook上です! »