ブラウザよりも高速アクセス！
16 関係: 単位元、単項演算、反復補題、形式言語、モノイド、オートマトン、スティーヴン・コール・クリーネ、空文字列、結合法則、生成 (数学)、EBNF、部分集合、閉包、連結、正規表現、文字列。
単位元
数学、とくに抽象代数学において、単位元（たんいげん, ）あるいは中立元（ちゅうりつげん, ）は、二項演算を備えた集合の特別な元で、ほかのどの元もその二項演算による単位元との結合の影響を受けない。.
新しい！!: クリーネ閉包と単位元 · 続きを見る »
単項演算
単項演算とは、数学で、被作用子（オペランド）が一つだけであるような演算（つまり、入力が一つの演算）のこと。 たとえば、論理否定は真理値に対する単項演算であり、自乗は実数に対する単項演算である。階乗 n! も単項演算である。与えられた集合 S に対する単項演算は、関数 S→S に他ならない。 単項演算は、プログラミング言語においても使われる（APLではmonadicという）。たとえば、C言語の系統では、以下の単項演算子がある。.
新しい！!: クリーネ閉包と単項演算 · 続きを見る »
反復補題
反復補題（英: Pumping lemma）とは、計算可能性理論において、あるクラスの形式言語に反復を施してもそのクラスに依然として属することを示すものである。ここでいう「反復」とは、その言語に含まれる十分に長い文字列が部分に分割可能で、その一部分を繰り返したさらに長い文字列も同じ言語に含まれるようにすることである。この補題の証明には、鳩の巣原理のような組合せ数学が必要とされる。 反復補題の重要な具体例として、正規言語の反復補題と文脈自由言語の反復補題がある。文脈自由言語の反復補題の一種として、オグデンの補題もある。 これらの補題は、ある言語が特定の言語クラスに属さないことを示すのに使われる。しかし逆に、反復補題を満たすことは必要条件ではあっても十分条件ではないので、ある言語があるクラスに属することを示すのには使えない。.
新しい！!: クリーネ閉包と反復補題 · 続きを見る »
形式言語
形式言語（けいしきげんご、formal language）は、その文法（構文、統語論）が、場合によっては意味（意味論）も、形式的に与えられている（形式体系を参照）言語である。形式的でないために、しばしば曖昧さが曖昧なまま残されたり、話者集団という不特定多数によってうつろいゆくような自然言語のそれに対して、一部の人工言語や、いわゆる機械可読な（機械可読目録を参照）ドキュメント類などは形式言語である。この記事では形式的な統語論すなわち構文の形式的な定義と形式文法について述べる。形式的な意味論については形式意味論の記事を参照。.
新しい！!: クリーネ閉包と形式言語 · 続きを見る »
モノイド
数学、とくに抽象代数学における単系（たんけい、monoid; モノイド）はひとつの二項演算と単位元をもつ代数的構造である。モノイドは単位元をもつ半群（単位的半群）であるので、半群論の研究対象の範疇に属する。 モノイドの概念は数学のさまざまな分野に現れる。たとえば、モノイドはそれ自身が「ただひとつの対象をもつ圏」と見ることができ、したがって「集合上の写像とその合成」といった概念を捉えたものと考えることもできる。モノイドの概念は計算機科学の分野でも、その基礎付けや実用プログラミングの両面で広く用いられる。 モノイドの歴史や、モノイドに一般的な性質を付加した議論などは半群の項に譲る。.
新しい！!: クリーネ閉包とモノイド · 続きを見る »
オートマトン
ートマトン (単数形: automaton, 複数形: オートマタ（automata ）) とは、自動人形などとも呼ばれる「オートマタ」と同じ語であるが、計算理論において、計算モデルに関して有限オートマトンなどの総称として使われる。また特に「オートマトン理論」と呼ばれる分野では、計算機械のうち計算可能性の点でチューリングマシンよりも制限されているものを特に指して言うこともある。.
新しい！!: クリーネ閉包とオートマトン · 続きを見る »
スティーヴン・コール・クリーネ
ティーヴン・コール・クリーネ（Stephen Cole Kleene, 1909年1月5日 - 1994年1月25日）は、アメリカの数学者。ウィスコンシン大学マディソン校に勤め、その業績は計算機科学の理論的な基礎を築くのに貢献した。クリーネは、正規表現の発明や、アロンゾ・チャーチ、クルト・ゲーデル、アラン・チューリング、エミール・ポストらと共に帰納的関数論という数理論理学の一分野を創始したことで知られる。クリーネ代数、クリーネ閉包、クリーネの再帰定理、クリーネ不動点定理の由来になっている。クリーネはまたライツェン・エヒベルトゥス・ヤン・ブラウワーが創始した数学的直観主義に貢献した。 クリーネは自分の姓をクレーニ（（IPA））と発音していた。英語圏ではクリーニ（）、クリーン（）などと誤読されることが多く、日本ではクリーネの表記が一般的になってしまっている。 その数理論理学における傑出した業績は、英語圏の論理学者の間に、"Cleanliness is next to godliness"「清潔さは信心深さに次ぐ」をもじって"Kleeneliness is next to Gödeliness"という格言があることにも表れている。.
新しい！!: クリーネ閉包とスティーヴン・コール・クリーネ · 続きを見る »
空文字列
形式言語理論における空文字列（くうもじれつ・からもじれつ、empty string）またはヌル文字列（null stringKernighan and Ritchie, C, p.38）とは、長さが0の一意な文字列であり、文字列における空集合である。主にコンピュータ、特にプログラミング言語において用いられる用語である。.
新しい！!: クリーネ閉包と空文字列 · 続きを見る »
結合法則
数学、殊に代数学における結合法則（けつごうほうそく、associative law) 、結合則、結合律あるいは演算の結合性（けつごうせい、associativity）は二項演算に対して考えられる性質の一つ。ひとつの数式にその演算の演算子が2個以上並んでいる時、その演算子について、左右どちらの側が優先されるかに関わらず結果が同じになるような演算は結合的 (associative) である。.
新しい！!: クリーネ閉包と結合法則 · 続きを見る »
生成 (数学)
数学における生成（せいせい、generate）とは、与えられた対象と条件に対して、その条件を満たしかつ与えられた対象を全て含むような最小の構成物を求めることである。このとき与えられた対象の集まりを生成系（生成集合）(generating set) といい、生成集合の各元を生成元 (generator) という。また、「最小の構成物」は生成系から生成されるという。生成系が1つの対象からなるような場合には、生成系と生成元は同一視できる。.
新しい！!: クリーネ閉包と生成 (数学) · 続きを見る »
EBNF
EBNF（Extended Backus–Naur Form）とは、文脈自由文法を表現するメタ文法記法であり、コンピュータのプログラミング言語や形式言語の形式的表現として使われる。バッカス・ナウア記法 (BNF) の拡張であり、拡張バッカス・ナウア記法とも呼ばれるが、ABNF（Augmented Backus-Naur Form）も同じ訳語となるため、区別するためあえて EBNF としている。 ニクラウス・ヴィルトが最初に開発した。EBNF の標準化されたものとして ISO-14977 などがある。.
新しい！!: クリーネ閉包とEBNF · 続きを見る »
部分集合
集合 A が集合 B の部分集合（ぶぶんしゅうごう、subset; 下位集合）であるとは、A が B の一部（あるいは全部）の要素だけからなることである。A が B の一部分であるという意味で部分集合という。二つの集合の一方が他方の部分集合であるとき、この二つの集合の間に包含関係があるという。.
新しい！!: クリーネ閉包と部分集合 · 続きを見る »
閉包
閉包（へいほう）とは次の意味の用語．.
連結
連結（れんけつ）とはつなぎ合わせること、またはつなぎ合わさっている性質のこと。.
正規表現
正規表現（せいきひょうげん、regular expression）とは、文字列の集合を一つの文字列で表現する方法の一つである。正則表現（せいそくひょうげん）とも呼ばれ、形式言語理論の分野では比較的こちらの訳語の方が使われる。まれに正規式と呼ばれることもある。 もともと正規表現は形式言語理論において正規言語を表すための手段として導入された。形式言語理論では、形式言語が正規言語であることと正規表現によって表せることは同値である。 その後正規表現はテキストエディタ、ワードプロセッサなどのアプリケーションで（ないし、そもそもそれ以前に単機能の文字列探索ツールの）、マッチさせるべき対象を表すために使用されるようになり、表せるパターンの種類を増やすために本来の正規表現にはないさまざまな記法が新たに付け加えられた。このような拡張された正規表現には正規言語ではない文字列も表せるものも多く、ゆえに正規表現という名前は実態に即していない面もあるが、伝統的に正規表現と呼ばれ続けている。 この記事では主にこのような正規表現を用いたパターンマッチングについて説明している。以下、誤解のない限り、アプリケーションやプログラミングにおいて正規表現を用いた文字列のパターンマッチングを行う機能のことを、単に正規表現という。 ほとんどのプログラミング言語では、ライブラリによって正規表現を使うことができる他、一部の言語では正規表現のリテラルもある。「正規表現によるマッチ」を意味する（専用の）演算子がある言語なども一部ある。具体例として、grep、AWK、sed、Perl、Tcl、lexなどがある。 それぞれの言語やアプリケーションで細部の仕様が異なっている、といったように思われることも多いが（また、古い実装では実際にそういうことも多いが）、近年は同じライブラリを使っていれば同じということも多い。またPOSIXなど標準もある。.
新しい！!: クリーネ閉包と正規表現 · 続きを見る »
文字列
文字列（もじれつ）は、単語や文章のような、文字の連なったもの。ストリング (string)、テキスト (text) という場合もある。コンピュータ、特にプログラミングの分野で用いることが多い。.
新しい！!: クリーネ閉包と文字列 · 続きを見る »
