84

言語レベルの概念（通常、文脈自由、文脈依存など）を理解しようとしています。

これは簡単に調べることができますが、私が見つけたすべての説明はたくさんの記号であり、セットについて話します。2つの質問があります：

  1. 正規言語とは何か、言語の違いを言葉で説明できますか？

  2. 人々はどこでこのことを理解することを学びますか？私が理解しているように、それは形式的な数学ですか？私はそれを使用する大学でいくつかのコースを持っていました、そして家庭教師がちょうど私たちがそれを知っていると思ったのでほとんど誰もそれを理解しませんでした。どこでそれを学ぶことができますか、そしてなぜ人々はそれを非常に多くの情報源で知ることを「期待」されているのですか？教育にギャップがあるようなものです。

次に例を示します。

このセットに属する言語はすべて、アルファベット上の正規言語です。

言語はどのようにして何かを「超える」ことができますか？

4

2 に答える 2

165

コンピュータ サイエンスの文脈では、単語は記号の連結です。使用される記号はアルファベットと呼ばれます。たとえば、アルファベットから形成されたいくつかの{0,1,2,3,4,5,6,7,8,9}単語は、、、、、、およびです。12125431000002

言語は、可能なすべての単語のサブセットです。たとえば、すべてのエリート MI6 エージェントをキャプチャする言語を定義したい場合があります。これらはすべて double-0 で始まるため、言語の単語は007、001、005、およびになりますが、またはではあり0012ません。簡単にするために、言語は「アルファベットの記号の連結によって形成される単語のサブセット」ではなく、「アルファベット上」であると言います。0715

コンピュータ サイエンスでは、言語を分類したいと考えています。単語内のすべての記号を次々と調べることによって、アルゴリズム/定数 (有限) メモリを備えたマシンを使用して単語が言語に含まれているかどうかを判断できる場合、その言語を正規と呼びます。42任意の量のメモリを必要とせずに単語が含まれているかどうかを判断できるため、単語だけで構成される言語は規則的です。最初の記号が 4 かどうか、2 番目の記号が 2 かどうか、さらに数字が続くかどうかを確認するだけです。

限られた数の単語を持つすべての言語は規則的です。これは、(理論的には) 一定サイズの制御フロー ツリーを構築できるためです ( if1 つの数字を次々と調べる入れ子になったステートメントの束として視覚化できます)。たとえば、単語が「10 から 99 までの素数」言語であるかどうかをテストするには、次の構成を使用します。現在のコード行でエンコードするメモリ以外はメモリを必要としません。

if word[0] == 1:
  if word[1] == 1: # 11
      return true # "accept" word, i.e. it's in the language
  if word[1] == 3: # 13
      return true
...
return false

すべての有限言語は正規ですが、すべての正規言語が有限であるとは限りません。私たちの double-0 言語には無数の単語 ( 007, 008, だけでなく004242andも含む0012345) が含まれていますが、一定のメモリでテストできます: 単語がそれに属しているかどうかをテストするには、最初の記号が0であるかどうか、および 2 番目の記号が であるかどうかを確認し0ます。その場合は、それを受け入れてください。単語が 3 より短い場合、または で始まらない場合00、それは MI6 コード名ではありません。

正式には、言語が規則的であることを証明するために、有限状態機械または規則的な文法の構造が使用されます。これらはif上記のステートメントに似ていますが、任意の長さの単語を許可します。有限状態マシンがある場合は通常の文法もあり、その逆もあるため、どちらかを示すだけで十分です。たとえば、double-0 言語の有限ステート マシンは次のとおりです。

start state:  if input = 0 then goto state 2
start state:  if input = 1 then fail
start state:  if input = 2 then fail
...
state 2: if input = 0 then accept
state 2: if input != 0 then fail
accept: for any input, accept

同等の通常の文法は次のとおりです。

start → 0 B
B → 0 accept
accept → 0 accept
accept → 1 accept
...

同等の正規表現は次のとおりです。

00[0-9]*

一部の言語は規則的ではありません。たとえば、任意の数の の1後に同数の が続く(任意のn2に対して1 n 2 nと表記されることが多い) 言語は規則的ではありません。一定量以上のメモリ (= 一定数の状態) が必要です。 ) の数を格納して、単語がその言語に含まれているかどうかを判断します。1

これは通常、理論的なコンピューター サイエンスのコースで説明する必要があります。幸いなことに、ウィキペディアでは、正式な言語と通常の言語の両方を非常にうまく説明しています。

于 2011-07-16T15:18:19.557 に答える
5

ウィキペディアの同等の定義の一部を次に示します。

[...]正規言語は、次の同等のプロパティを満たす形式言語（つまり、有限のアルファベットからの記号の有限のシーケンスのおそらく無限のセット）です。

  • それは決定論的な有限状態マシンによって受け入れられます。

  • 非決定論的な有限状態マシンによって受け入れられる可能性があります

  • 正式な正規表現で記述できます。

    多くのプログラミング言語で提供される「正規表現」機能は、正規ではない言語を認識できるようにする機能によって拡張されていることに注意してください。したがって、正式な正規表現と厳密には同等ではありません。

最初に注意すべきことは、通常の言語は形式的な言語であり、いくつかの制限があるということです。形式言語は、本質的には文字列の (場合によっては無限の) コレクションです。たとえば、形式言語 Java は、考えられるすべての Java ファイルのコレクションであり、考えられるすべてのテキスト ファイルのコレクションのサブセットです。

最も重要な特徴の 1 つは、文脈自由言語とは異なり、通常の言語は任意の入れ子/再帰をサポートしていませんが、任意の繰り返しがあることです。

言語には常に、許可されている記号のセットである基礎となるアルファベットがあります。たとえば、プログラミング言語のアルファベットは通常、ASCII または Unicode のいずれかですが、正式な言語理論では、他のアルファベットよりも言語について話すことも問題ありませ0ん1。

私の大学では、コンパイラのクラスで形式的な言語理論を教えられましたが、これはおそらく学校によって異なるでしょう。

于 2011-07-16T15:17:38.080 に答える