6

これはプログラミングの質問というよりはコンピュータサイエンスの質問ですが、関連するすべてのサイトの中でこれを尋ねるのに最適な場所だと思います。

正規表現を発見して用語を調べたとき、この「正規表現」の特性は、表現の言語が定義可能な構造パターンを持っているという事実を指していると思いました。しかし、この主題とその背後にある理論について読んだときに、規則的ではない種類の言語があることを学びましたが、それらの定義方法から、パターンをそれらに一致させることができることは明らかです。そのような言語の1つは(a ^ n)(b ^ n)です。明らかにこれはパターンですが、これは正規言語ではありません。だから今、私はそれらを正規にするのは正規言語について何であるのか疑問に思っていますが、この言語はそうではありませんか?

4

5 に答える 5

11

コンピュータサイエンスを直感的に説明するのは...注意が必要です。試してみますが、これの一部は「十分に近い」ものになるが、理論的には厳密ではないことに注意してください。

正規言語は、有限オートマトン(DFA / NDFA)と計算上同等のマシンで決定できる言語です。有限オートマトンは、ストレージがなく、純粋に状態で動作するマシンと考えることができます。したがって、a n b nは、それらを比較するためにaとbの数をカウントできる(したがって、無限の*ストレージ容量が必要)マシンを必要とするため、規則的ではないことがわかります。

比較のために、繰り返しの数は無関係であるため、(abc) n は規則的です。

より厳密な(そしてそれに応じてより密度の高いビュー)については、ウィキペディアの記事とリンクされたページを確認してください。

*ここでは無限は関係ありませんが、完全を期すために言及します。「幸運なことに、常に十分な」ストレージと考える方が簡単かもしれません。

于 2010-01-09T02:05:59.690 に答える
4

名前の語源は、目的のために作成された彼の数学表記を使用して通常のセットを説明するKleeneの1950年代の作品に由来します。これを参照してください。

于 2010-01-09T01:56:23.810 に答える
1

おそらく、正規言語に関するウィキペディアの記事は、私たちよりもうまく説明できるでしょう。しかし、私はそれを試してみます。

理論的な観点から、正規言語(文字列のセット)は、有限状態オートマトンを使用して生成できる言語です。プログラマーの用語では、これは正規表現を使用して生成できると言うのと同じです。したがって、すべての有限言語(文字列のセット)は正規表現ですが、FSAまたは正規表現を使用して認識できないn b n (naの後にnbが続くすべての文字列の言語)などのいくつかの無限言語があります。式。これらの言語を認識できる、より強力な計算デバイス(チューリングマシンを使用してモデル化された最新のコンピューターなど)があります。

文字列検索のプログラミングで正規表現が多く使用される理由は、プログラマーにとって重要な文字列の大部分を認識できると同時に、有限状態オートマトンを使用して非常に迅速に検索するように実装できるためです。

于 2010-01-09T02:04:57.040 に答える
0

の単語regularregular expression、英語の概念ではなく、通常の数学的概念を指します。prime数学の言葉がプライムビーフとほとんど関係がないのと同じように。

より具体的な概念を参照するために、CS(数学の分野)に継承されています:http://en.wikipedia.org/wiki/Regular_language

于 2010-01-09T02:03:01.187 に答える
0

正規表現は実際には規則的ではなく、名前は語源です。

于 2010-01-09T02:03:58.060 に答える