ブラウザよりも高速アクセス！
22 関係: 句構造文法、帰納的可算言語、帰納言語、形式言語、形式言語の階層、形式文法、ノーム・チョムスキー、チューリングマシン、プログラミング言語、プッシュダウン・オートマトン、線形拘束オートマトン、終端記号と非終端記号、部分集合、正規表現、正規言語、正規文法、有限オートマトン、有限集合、文脈依存言語、文脈依存文法、文脈自由言語、文脈自由文法。
句構造文法
句構造文法（くこうぞうぶんぽう、、PSG）は、句構造規則で定義された文法を指す用語としてノーム・チョムスキーが考案したもので、エミール・ポストと Axel Thue が研究したかたちの書き換え規則の集まりである（）。チョムスキー階層の文脈依存文法または文脈自由文法のみを指す用語として使うこともある。広義の句構造文法は「構成文法」(constituency grammar) とも呼ばれる。これは句構造文法が構成関係 (constituency relation) に着目したもので、依存関係 (dependency relation) に着目した依存文法と対比されるものだからである。.
新しい！!: チョムスキー階層と句構造文法 · 続きを見る »
帰納的可算言語
帰納的可算言語（きのうてきかさんげんご、Recursively enumerable language）は、数学・論理学・計算機科学における形式言語の一種である。部分決定性言語（Partially Decidable Language）、チューリング受理性言語（Turing-recognizable Language）とも呼ぶ。形式言語のチョムスキー階層におけるタイプ-0言語に相当する。全ての帰納的可算言語は複雑性クラス RE に属する。.
新しい！!: チョムスキー階層と帰納的可算言語 · 続きを見る »
帰納言語
帰納言語（きのうげんご、Recursive language）は、数学・論理学・計算機科学における形式言語の一種である。決定性言語(Decidable Language)、チューリング決定性言語(Turing-decidable Language)とも呼ぶ。全ての帰納言語の属する複雑性クラスをRと呼ぶが、RPクラスを Rと呼ぶこともある。 このクラスの言語はチョムスキー階層では定義されていない（Chomsky 1959）。.
新しい！!: チョムスキー階層と帰納言語 · 続きを見る »
形式言語
形式言語（けいしきげんご、formal language）は、その文法（構文、統語論）が、場合によっては意味（意味論）も、形式的に与えられている（形式体系を参照）言語である。形式的でないために、しばしば曖昧さが曖昧なまま残されたり、話者集団という不特定多数によってうつろいゆくような自然言語のそれに対して、一部の人工言語や、いわゆる機械可読な（機械可読目録を参照）ドキュメント類などは形式言語である。この記事では形式的な統語論すなわち構文の形式的な定義と形式文法について述べる。形式的な意味論については形式意味論の記事を参照。.
新しい！!: チョムスキー階層と形式言語 · 続きを見る »
形式言語の階層
形式言語の階層は形式言語の包含階層で、計算理論や形式言語学などにおいて研究される。計算複雑性理論の記述計算量や複雑性クラスとも密接に関係する。1956年に発表されたチョムスキー階層に始まるが、その後の（主に計算理論とその周辺分野での）研究により、一般化・細分化が進められた。また、この包含階層の一部を可算個に分ける階層も幾つか知られている。.
新しい！!: チョムスキー階層と形式言語の階層 · 続きを見る »
形式文法
形式文法（けいしきぶんぽう、Formal Grammar）は、形式的に与えられた（形式体系を参照）文法である。「言語」をその言語における文の集合として与えるものとして、ここでは、（有限の）文字群上の有限長の文字列の（通常無限な）集合が、形式的に記述される。 形式文法にはふたつの捉えかたがある。それは「生成」と「分析」である。#チョムスキー階層の節および単独記事に詳細があるが、両者は対応するので、ある意味では同じものをそれぞれ逆の側から見たものにすぎない。 以下で「文法の規則（構文規則）の集まり」と呼んでいるのは、具体的には、句構造規則#基本モデルにあるようなものである。また終端記号と非終端記号の記事も参照のこと。.
新しい！!: チョムスキー階層と形式文法 · 続きを見る »
ノーム・チョムスキー
イヴラム・ノーム・チョムスキー（、1928年12月7日 - ）は、アメリカ合衆国の哲学者, by Zoltán Gendler Szabó, in Dictionary of Modern American Philosophers, 1860–1960, ed.
新しい！!: チョムスキー階層とノーム・チョムスキー · 続きを見る »
チューリングマシン
チューリングマシン (Turing Machine) は計算模型のひとつで、計算機を数学的に議論するための単純化・理想化された仮想機械である。.
新しい！!: チョムスキー階層とチューリングマシン · 続きを見る »
プログラミング言語
プログラミング言語（プログラミングげんご、programming language）とは、コンピュータプログラムを記述するための形式言語である。なお、コンピュータ以外にもプログラマブルなものがあることを考慮するならば、この記事で扱っている内容については、「コンピュータプログラミング言語」（computer programming language）に限定されている。.
新しい！!: チョムスキー階層とプログラミング言語 · 続きを見る »
プッシュダウン・オートマトン
プッシュダウン・オートマトン（Pushdown Automaton）は、オートマトンの一種であり、文脈自由言語を認識する抽象機械である。 ある意味では、プッシュダウン・オートマトンは有限オートマトンと無限の容量のスタックを組み合せたシステムである。.
新しい！!: チョムスキー階層とプッシュダウン・オートマトン · 続きを見る »
線形拘束オートマトン
線形拘束オートマトン（せんけいこうそくオートマトン、Linear Bounded Automaton）は、制限されたチューリングマシンである。LBA と略記される。有限種類の文字を保持できるテープとそのテープの読み書きができるヘッドを持ち、有限数の状態を持つ。チューリングマシンと異なるのは LBA のテープ長が有限であることで、その長さはテープ上の初期入力文字列の長さに比例する（つまり一次関数である）。この制限により LBA はある意味ではチューリングマシンよりも実在のコンピュータの正確なモデルと言える。 線形拘束オートマトンは文脈依存言語を受容する。そのクラスの言語の文法で制限されていることは、ある文字列から短い別の文字列へのマッピングを持たないことである。したがって、文脈依存言語によって生成される文字列は、それ自身より長い文型を内包することができない。線形拘束オートマトンと文脈依存言語は一対一の対応関係にあるので、本来の文字列が書かれたテープの長さがあれば、そのオートマトンに理解できる文字列には必要十分である。.
新しい！!: チョムスキー階層と線形拘束オートマトン · 続きを見る »
終端記号と非終端記号
終端記号（しゅうたんきごう、Terminal symbol）と非終端記号（ひしゅうたんきごう、Nonterminal symbol）は、句構造規則の生成規則中にあらわれる記号類の分類である。規則群のうちの、どれかの規則の左辺にあらわれている記号、すなわち、他の記号列と置換できるものとして定義されている記号が非終端記号で、ある種の変数名のようなものとも言える。それに対し、右辺の記号列中のみにあらわれる、いわゆる「アルファベット」の1文字から成る記号が終端記号である。実用上は（プログラミング言語などでは）終端記号は文字そのものではなく、英語などにおける「単語」に相当する「トークン」と呼ばれるもの（「字句」の記事、および字句解析#トークンなどを参照）であることも多い。.
新しい！!: チョムスキー階層と終端記号と非終端記号 · 続きを見る »
部分集合
集合 A が集合 B の部分集合（ぶぶんしゅうごう、subset; 下位集合）であるとは、A が B の一部（あるいは全部）の要素だけからなることである。A が B の一部分であるという意味で部分集合という。二つの集合の一方が他方の部分集合であるとき、この二つの集合の間に包含関係があるという。.
新しい！!: チョムスキー階層と部分集合 · 続きを見る »
正規表現
正規表現（せいきひょうげん、regular expression）とは、文字列の集合を一つの文字列で表現する方法の一つである。正則表現（せいそくひょうげん）とも呼ばれ、形式言語理論の分野では比較的こちらの訳語の方が使われる。まれに正規式と呼ばれることもある。 もともと正規表現は形式言語理論において正規言語を表すための手段として導入された。形式言語理論では、形式言語が正規言語であることと正規表現によって表せることは同値である。 その後正規表現はテキストエディタ、ワードプロセッサなどのアプリケーションで（ないし、そもそもそれ以前に単機能の文字列探索ツールの）、マッチさせるべき対象を表すために使用されるようになり、表せるパターンの種類を増やすために本来の正規表現にはないさまざまな記法が新たに付け加えられた。このような拡張された正規表現には正規言語ではない文字列も表せるものも多く、ゆえに正規表現という名前は実態に即していない面もあるが、伝統的に正規表現と呼ばれ続けている。 この記事では主にこのような正規表現を用いたパターンマッチングについて説明している。以下、誤解のない限り、アプリケーションやプログラミングにおいて正規表現を用いた文字列のパターンマッチングを行う機能のことを、単に正規表現という。 ほとんどのプログラミング言語では、ライブラリによって正規表現を使うことができる他、一部の言語では正規表現のリテラルもある。「正規表現によるマッチ」を意味する（専用の）演算子がある言語なども一部ある。具体例として、grep、AWK、sed、Perl、Tcl、lexなどがある。 それぞれの言語やアプリケーションで細部の仕様が異なっている、といったように思われることも多いが（また、古い実装では実際にそういうことも多いが）、近年は同じライブラリを使っていれば同じということも多い。またPOSIXなど標準もある。.
新しい！!: チョムスキー階層と正規表現 · 続きを見る »
正規言語
正規言語（せいきげんご）または正則言語（せいそくげんご）は、以下に示す性質（いずれも等価）を満たす形式言語である。.
新しい！!: チョムスキー階層と正規言語 · 続きを見る »
正規文法
正規文法（せいきぶんぽう、Regular Grammar）は、形式文法における右正規文法と左正規文法の総称。 右正規文法（みぎせいきぶんぽう、Right Regular Grammar）は、形式文法(N, Σ, P, S) において P に含まれる生成規則が以下のような形式になっているものである。.
新しい！!: チョムスキー階層と正規文法 · 続きを見る »
有限オートマトン
有限オートマトン（finite automaton)または有限状態機械（finite state machine, FSM）とは、有限個の状態と遷移と動作の組み合わせからなる数学的に抽象化された「ふるまいのモデル」である。デジタル回路やプログラムの設計で使われることがあり、ある一連の状態をとったときどのように論理が流れるかを調べることができる。有限個の「状態」のうち1つの状態をとる。ある時点では1つの状態しかとらず、それをその時点の「現在状態」と呼ぶ。何らかのイベントや条件によってある状態から別の状態へと移行し、それを「遷移」と呼ぶ。それぞれの現在状態から遷移しうる状態と、遷移のきっかけとなる条件を列挙することで定義される。 有限オートマトンは様々な問題に応用でき、半導体設計の自動化、通信プロトコル設計、構文解析などの工学面での応用がある。生物学や人工知能研究では状態機械（群）を使って神経系をモデル化し、言語学では自然言語の文法をモデル化したりする。.
新しい！!: チョムスキー階層と有限オートマトン · 続きを見る »
有限集合
数学において、集合が有限（ゆうげん、finite）であるとは、自然数 n を用いて という形にあらわされる集合との間に全単射が存在することをいう（ただしここでは、n.
新しい！!: チョムスキー階層と有限集合 · 続きを見る »
文脈依存言語
文脈依存言語（ぶんみゃくいそんげんご、Context-sensitive Language）は、文脈依存文法で定義される形式言語である。これはチョムスキー階層の四つの文法のひとつであるが、理論的にも実用的にも最も使われることが少ない文法でもある。.
新しい！!: チョムスキー階層と文脈依存言語 · 続きを見る »
文脈依存文法
文脈依存文法（ぶんみゃくいぞんぶんぽう、Context-sensitive Grammar）は、形式文法 G.
新しい！!: チョムスキー階層と文脈依存文法 · 続きを見る »
文脈自由言語
文脈自由言語（ぶんみゃくじゆうげんご）とは、次のような再帰的な生成規則をもつ文脈自由文法によって、与えられた言語の長さ n に対して O(n3) の時間で認識される形式言語。プッシュダウン・オートマトンで受理可能な言語と等価である。.
新しい！!: チョムスキー階層と文脈自由言語 · 続きを見る »
文脈自由文法
文脈自由文法（ぶんみゃくじゆうぶんぽう、Context-free Grammar、CFG）は、形式言語の理論（特に、生成文法）において全生成規則が以下のようである形式文法である。 ここで V は非終端記号であり、w は終端記号と非終端記号の（0個を含む）任意個の並びである。「文脈自由」という用語は前後関係に依存せずに非終端記号 V を w に置換できる、という所から来ている（「文脈無用」という訳の提案もある）。文脈自由文法によって生成される形式言語を文脈自由言語という。.
新しい！!: チョムスキー階層と文脈自由文法 · 続きを見る »
