正規言語と決定性有限オートマトン間の類似点
正規言語と決定性有限オートマトンは(ユニオンペディアに)共通で4ものを持っています: 形式言語、チューリングマシン、非決定性有限オートマトン、正規表現。
形式言語
形式言語(けいしきげんご、formal language)は、その文法(構文、統語論)が、場合によっては意味(意味論)も、形式的に与えられている(形式体系を参照)言語である。形式的でないために、しばしば曖昧さが曖昧なまま残されたり、話者集団という不特定多数によってうつろいゆくような自然言語のそれに対して、一部の人工言語や、いわゆる機械可読な(機械可読目録を参照)ドキュメント類などは形式言語である。この記事では形式的な統語論すなわち構文の形式的な定義と形式文法について述べる。形式的な意味論については形式意味論の記事を参照。.
形式言語と正規言語 · 形式言語と決定性有限オートマトン ·
チューリングマシン
チューリングマシン (Turing Machine) は計算模型のひとつで、計算機を数学的に議論するための単純化・理想化された仮想機械である。.
チューリングマシンと正規言語 · チューリングマシンと決定性有限オートマトン ·
非決定性有限オートマトン
非決定性有限オートマトン()または非決定性有限状態機械()は、有限オートマトンの一種であり、ある状態と入力があったとき、次の遷移先が一意に決定しないことがあるものである。NFAと略記される。.
正規言語と非決定性有限オートマトン · 決定性有限オートマトンと非決定性有限オートマトン ·
正規表現
正規表現(せいきひょうげん、regular expression)とは、文字列の集合を一つの文字列で表現する方法の一つである。正則表現(せいそくひょうげん)とも呼ばれ、形式言語理論の分野では比較的こちらの訳語の方が使われる。まれに正規式と呼ばれることもある。 もともと正規表現は形式言語理論において正規言語を表すための手段として導入された。形式言語理論では、形式言語が正規言語であることと正規表現によって表せることは同値である。 その後正規表現はテキストエディタ、ワードプロセッサなどのアプリケーションで(ないし、そもそもそれ以前に単機能の文字列探索ツールの)、マッチさせるべき対象を表すために使用されるようになり、表せるパターンの種類を増やすために本来の正規表現にはないさまざまな記法が新たに付け加えられた。このような拡張された正規表現には正規言語ではない文字列も表せるものも多く、ゆえに正規表現という名前は実態に即していない面もあるが、伝統的に正規表現と呼ばれ続けている。 この記事では主にこのような正規表現を用いたパターンマッチングについて説明している。以下、誤解のない限り、アプリケーションやプログラミングにおいて正規表現を用いた文字列のパターンマッチングを行う機能のことを、単に正規表現という。 ほとんどのプログラミング言語では、ライブラリによって正規表現を使うことができる他、一部の言語では正規表現のリテラルもある。「正規表現によるマッチ」を意味する(専用の)演算子がある言語なども一部ある。具体例として、grep、AWK、sed、Perl、Tcl、lexなどがある。 それぞれの言語やアプリケーションで細部の仕様が異なっている、といったように思われることも多いが(また、古い実装では実際にそういうことも多いが)、近年は同じライブラリを使っていれば同じということも多い。またPOSIXなど標準もある。.
上記のリストは以下の質問に答えます
- 何正規言語と決定性有限オートマトンことは共通しています
- 何が正規言語と決定性有限オートマトン間の類似点があります
正規言語と決定性有限オートマトンの間の比較
決定性有限オートマトンが10を有している正規言語は、15の関係を有しています。 彼らは一般的な4で持っているように、ジャカード指数は16.00%です = 4 / (15 + 10)。
参考文献
この記事では、正規言語と決定性有限オートマトンとの関係を示しています。情報が抽出された各記事にアクセスするには、次のURLをご覧ください: