smn定理 - Wikipedia
smn定理 (英: smn theorem) もしくはパラメータ定理 (英: parameterization theorem) とは、再帰理論における定理であり、プログラミング言語（より一般化すれば、計算可能関数のゲーデル数）の基盤となっている[1][2]。これを最初に証明したのはスティーブン・コール・クリーネである[3]。s-m-n定理と表記されることもある。 この定理を実用的に解説すると、あるプログラミング言語と正の整数 m と n があるとき、m+n 個の自由変数を持つプログラムのソースコードを操作する特定のアルゴリズムがあることを示している。そのアルゴリズムは、与えられた m 個の値を最初の m 個の自由変数に束縛し、残りの変数を自由変数のままにしておく。 詳細[編集] 本定理の基本形は、2引数の関数に適用される。再帰関数のゲーデル数 が与えられたとき、次のような性質の2引数の原
帰納言語 - Wikipedia
帰納言語（きのうげんご、英: Recursive language）は、数学・論理学・計算機科学における形式言語の一種である。決定性言語(Decidable Language)、チューリング決定性言語(Turing-decidable Language)とも呼ぶ。全ての帰納言語の属する複雑性クラスをRと呼ぶが、RPクラスを Rと呼ぶこともある。 このクラスの言語はチョムスキー階層では定義されていない（Chomsky 1959）。 帰納言語の定義には以下の2つの等価な定義がある。 帰納言語は、形式言語のアルファベットにおける全ての単語の集合のうちの帰納的部分集合である。 帰納言語は、その言語を受容するチューリングマシンがあったとき、その言語に属する文字列を入力したとき常に停止して受容し、属さない文字列を入力したとき常に停止して拒絶するような言語である。つまり、このチューリングマシンは常に停止
形式言語 - Wikipedia
形式言語（けいしきげんご、英: formal language）は、その文法（構文、統語論）が、場合によっては意味（意味論）も、形式的に与えられている（形式体系を参照）言語である。形式的でないために、しばしば曖昧さが残されたり、話者集団によって用法のうつろいゆくような自然言語に対して、プログラミング言語を含む一部の人工言語や、いわゆる機械可読な（機械可読目録を参照）ドキュメント類などの形式言語は、用法の変化に関しては厳格である。この記事では形式的な統語論すなわち構文の形式的な定義と形式文法について述べる。形式的な意味論については形式意味論の記事を参照。 定義[編集] 形式言語の理論、特にオートマトン理論と関連したそれにおいては、言語はアルファベットの列（語 word） の集合である[1]。 ただし、長さゼロの空単語（Empty Word, 記号 、、）も含む。 チューリングマシンの言語は単
黒田標準形 - Wikipedia
形式言語理論において、ある形式文法の全ての生成規則が次のいずれかの形式をもつとき、その文法は黒田標準形（くろだひょうじゅんけい、Kuroda normal form）であるという。 AB → CD A → BC A → B A → a ここで A, B, C, D は非終端記号であり a は終端記号である[1]。A → B はしばしば省略される[2]。 言語学者黒田成幸の研究に基づくが、黒田自身はこれを線形有界文法（linear bounded grammar）と呼んだ[3]。 黒田標準形をもつどんな文法も単調文法（英語版）であり、したがって文脈依存言語を生成する。逆に、空文字列を含まないどんな文脈依存言語も、黒田標準形をもつ文法によって生成することができる[2]。 György Révészによる素直な手法は、黒田標準形をチョムスキーの文脈依存文法の形に変換する。AB → CD は4個の
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
A Course in Formal Languages, Automata and Groups
