[解決済み] 正規の言語とは？

質問

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

私はこれを簡単に調べることができますが、私が見つけるすべての説明は、記号の負荷であり、次のように話しています。 セット . 私は2つの質問があります。

1. 正規の言語とは何か、言語はどのように違うのか、言葉で説明できますか？

2. このようなことを理解するために、人々はどこで学ぶのでしょうか？私が理解しているように、それは形式的な数学ですか？私はそれを使用する大学でのコースのカップルがあったし、チューターがちょうど私たちがそれを知っていると仮定して、ほとんど誰もそれを理解していませんでした。どこで学べるのでしょうか。また、なぜ人々は多くの情報源でそれを知ることが期待されているのでしょうか。 まるで教育にギャップがあるようです。

ここで の例です。 :

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

言語はどのように"over"することができますか？

どのように解決するのですか？

コンピュータサイエンスの文脈では 単語 を連結したものです。 シンボル . 使用される記号は アルファベット . 例えば、アルファベットから形成されるいくつかの単語は {0,1,2,3,4,5,6,7,8,9} は 1 , 2 , 12 , 543 , 1000 そして 002 .

A 言語 は、すべての可能な単語のサブセットです。たとえば、MI6のエリートエージェントをすべて捕捉する言語を定義することができます。これらはすべて double-0 で始まるので、言語内の単語は次のようになります。 007 , 001 , 005 そして 0012 ではなく 07 または 15 . 簡単のために、ある言語を " と呼びます。 以上 の代わりにアルファベットとします。 で an alphabet"です。

コンピュータサイエンスでは、現在、言語を分類したいと考えています。私たちは言語を 正規 と呼びます。ある単語がその言語に含まれるかどうかを、その単語に含まれるすべての記号を次々に調べることによって、一定の（有限の）メモリを持つアルゴリズム／機械で決定できる場合です。単語だけからなる言語 42 は、最初の記号が 4 かどうか、2 番目の記号が 2 かどうか、そしてさらに数字が続くかどうかをチェックするだけで、任意の量のメモリを必要とせずに単語が含まれているかどうかを決定できるので、規則的である。

有限個の単語を持つすべての言語は規則的です。なぜなら、（理論的には）一定の大きさの制御フローツリーを構築するだけだからです（ネストされた多くの if -ステートメントを入れ子にして、一桁ずつ調べていくようなイメージです）。たとえば、ある単語が 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

すべての有限言語は規則的であるが、すべての規則的な言語が有限であるわけではないことに注意してください。 007 , 008 を含むが、さらに 004242 と 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 の後に、同じ数の 2 (しばしば1 ⁿ 2 ⁿ の場合、任意の n の数を格納するために、一定量以上のメモリ（＝一定数の状態）が必要です。 1 の数を記憶して、ある単語が言語内にあるかどうかを判断するためには、一定量以上のメモリ（＝一定数の状態）が必要です。

これは通常、理論的なコンピュータサイエンスのコースで説明されるはずです。幸いなことに、Wikipediaには両方の説明があります。 形式 と 正規言語 を非常にうまく使っています。