ブラウザよりも高速アクセス！
15 関係: 単集合、同値、同値関係、形式言語、マイヒル–ネローデの定理、チューリングマシン、チョムスキー階層、クリーネ閉包、非決定性有限オートマトン、部分集合、正規表現、正規言語の反復補題、正規文法、決定性有限オートマトン、文脈自由言語。
単集合
数学における単集合（たんしゅうごう、singleton; 単元集合、単項集合、一元集合）あるいは単位集合（）は、唯一の元からなる集合である。一つ組 (1-tuple) や単項列 (a sequence with one element) と言うこともできる。 例えば、 という集合は単集合である。.
同値
同値（どうち）または等価（とうか）とは、2つの命題が共に真または共に偽のときに真となる論理演算である。 英語ではequivalence (EQ)。「if and only if」を略して、iff ともいう。否定排他的論理和 (XNOR) に等しい。 演算子記号は ⇔、↔、≡、.
同値関係
数学において、同値関係（どうちかんけい、equivalence relation）は反射的、対称的かつ推移的な二項関係を言う。これらの性質の帰結として、与えられた集合において、一つの同値関係はその集合を同値類に分割（類別）する。 同値関係にあることを表す記法は文献によって様々に用いられるけれども、与えられた集合上の同値関係 に関して二元 が同値であることを "" や "" で表すのがもっともよく用いられる記法である。 に関して同値であることを明示する場合には、"" や "" あるいは "" などと書かれる。.
形式言語
形式言語（けいしきげんご、formal language）は、その文法（構文、統語論）が、場合によっては意味（意味論）も、形式的に与えられている（形式体系を参照）言語である。形式的でないために、しばしば曖昧さが曖昧なまま残されたり、話者集団という不特定多数によってうつろいゆくような自然言語のそれに対して、一部の人工言語や、いわゆる機械可読な（機械可読目録を参照）ドキュメント類などは形式言語である。この記事では形式的な統語論すなわち構文の形式的な定義と形式文法について述べる。形式的な意味論については形式意味論の記事を参照。.
マイヒル–ネローデの定理
マイヒル–ネローデの定理（英: Myhill–Nerode theorem）とは、ある形式言語が正規言語であるための必要十分条件を提示した定理である。ほとんどの場合、ある言語が正規言語でないことを証明するのに使われる。 名称は1958年にこの定理を発見したシカゴ大学の John Myhill と Anil Nerode が由来である。.
新しい！!: 正規言語とマイヒル–ネローデの定理 · 続きを見る »
チューリングマシン
チューリングマシン (Turing Machine) は計算模型のひとつで、計算機を数学的に議論するための単純化・理想化された仮想機械である。.
新しい！!: 正規言語とチューリングマシン · 続きを見る »
チョムスキー階層
チョムスキー階層（チョムスキーかいそう、Chomsky Hierarchy）は、形式言語を生成する形式文法の包含階層（「形式言語の階層」）で、「句構造文法（Phrase Structure Grammars）の階層」などとも言う。1956年にノーム・チョムスキーが発表した。.
新しい！!: 正規言語とチョムスキー階層 · 続きを見る »
クリーネ閉包
リーネ閉包（くりーねへいほう、Kleene closure）は、形式言語とオートマトンの理論において、ある演算の繰り返しが「生成」するシンボルないし文字の列（文字列）の集合である。また、この繰り返しの単項演算子をクリーネスター（Kleene star）という。 集合 V に対するクリーネ閉包の適用は、V* と表す。スティーヴン・コール・クリーネがある種のオートマトンを特徴付けるために導入した方法である、正規表現でよく用いられる。.
新しい！!: 正規言語とクリーネ閉包 · 続きを見る »
非決定性有限オートマトン
非決定性有限オートマトン（）または非決定性有限状態機械（）は、有限オートマトンの一種であり、ある状態と入力があったとき、次の遷移先が一意に決定しないことがあるものである。NFAと略記される。.
新しい！!: 正規言語と非決定性有限オートマトン · 続きを見る »
部分集合
集合 A が集合 B の部分集合（ぶぶんしゅうごう、subset; 下位集合）であるとは、A が B の一部（あるいは全部）の要素だけからなることである。A が B の一部分であるという意味で部分集合という。二つの集合の一方が他方の部分集合であるとき、この二つの集合の間に包含関係があるという。.
正規表現
正規表現（せいきひょうげん、regular expression）とは、文字列の集合を一つの文字列で表現する方法の一つである。正則表現（せいそくひょうげん）とも呼ばれ、形式言語理論の分野では比較的こちらの訳語の方が使われる。まれに正規式と呼ばれることもある。 もともと正規表現は形式言語理論において正規言語を表すための手段として導入された。形式言語理論では、形式言語が正規言語であることと正規表現によって表せることは同値である。 その後正規表現はテキストエディタ、ワードプロセッサなどのアプリケーションで（ないし、そもそもそれ以前に単機能の文字列探索ツールの）、マッチさせるべき対象を表すために使用されるようになり、表せるパターンの種類を増やすために本来の正規表現にはないさまざまな記法が新たに付け加えられた。このような拡張された正規表現には正規言語ではない文字列も表せるものも多く、ゆえに正規表現という名前は実態に即していない面もあるが、伝統的に正規表現と呼ばれ続けている。 この記事では主にこのような正規表現を用いたパターンマッチングについて説明している。以下、誤解のない限り、アプリケーションやプログラミングにおいて正規表現を用いた文字列のパターンマッチングを行う機能のことを、単に正規表現という。 ほとんどのプログラミング言語では、ライブラリによって正規表現を使うことができる他、一部の言語では正規表現のリテラルもある。「正規表現によるマッチ」を意味する（専用の）演算子がある言語なども一部ある。具体例として、grep、AWK、sed、Perl、Tcl、lexなどがある。 それぞれの言語やアプリケーションで細部の仕様が異なっている、といったように思われることも多いが（また、古い実装では実際にそういうことも多いが）、近年は同じライブラリを使っていれば同じということも多い。またPOSIXなど標準もある。.
正規言語の反復補題
正規言語の反復補題（英: Pumping lemma for regular languages）とは、全ての正規言語が持つ属性を与える補題である。反復補題一般の具体例の一つである。その主たる用法は、ある言語が正規言語でないことを証明することである。 この反復補題は1961年に Y. Bar-Hillel、M.
新しい！!: 正規言語と正規言語の反復補題 · 続きを見る »
正規文法
正規文法（せいきぶんぽう、Regular Grammar）は、形式文法における右正規文法と左正規文法の総称。 右正規文法（みぎせいきぶんぽう、Right Regular Grammar）は、形式文法(N, Σ, P, S) において P に含まれる生成規則が以下のような形式になっているものである。.
決定性有限オートマトン
決定性有限オートマトン（けっていせいゆうげんオートマトン、Deterministic Finite Automaton）または決定性有限状態機械（けっていせいゆうげんじょうたいきかい、Deterministic Finite State Machine）は、状態と入力によって次に遷移すべき状態が一意に定まる有限オートマトンである。DFA と略記される。 DFAは入力文字列を受け付ける。各入力文字について、遷移関数にしたがって新たな状態に遷移する。最後に入力文字を受け付けたとき、受理状態であれば入力文字列は受理された、そうでなければ入力文字列は拒否されたと判断される。 非決定性有限オートマトンは、決定性有限オートマトンと同じように正規集合を認識でき、必ず決定性オートマトンに変換できる。.
新しい！!: 正規言語と決定性有限オートマトン · 続きを見る »
文脈自由言語
文脈自由言語（ぶんみゃくじゆうげんご）とは、次のような再帰的な生成規則をもつ文脈自由文法によって、与えられた言語の長さ n に対して O(n3) の時間で認識される形式言語。プッシュダウン・オートマトンで受理可能な言語と等価である。.
新しい！!: 正規言語と文脈自由言語 · 続きを見る »
ここにリダイレクトされます：
正則言語。
