帰納言語 - Wikipedia
帰納言語（きのうげんご、英: Recursive language）は、数学・論理学・計算機科学における形式言語の一種である。決定性言語(Decidable Language)、チューリング決定性言語(Turing-decidable Language)とも呼ぶ。全ての帰納言語の属する複雑性クラスをRと呼ぶが、RPクラスを Rと呼ぶこともある。 このクラスの言語はチョムスキー階層では定義されていない（Chomsky 1959）。 帰納言語の定義には以下の2つの等価な定義がある。 帰納言語は、形式言語のアルファベットにおける全ての単語の集合のうちの帰納的部分集合である。 帰納言語は、その言語を受容するチューリングマシンがあったとき、その言語に属する文字列を入力したとき常に停止して受容し、属さない文字列を入力したとき常に停止して拒絶するような言語である。つまり、このチューリングマシンは常に停止
黒田標準形 - 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ページを開く
