規則性とは何ですか？

Question

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

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

Answer 1

名前の語源は、目的のために作成彼の数学的な表記法を使用して、の定期的なセットを記述するクリーネの1950年代の作品から来ています。 こののを参照してください。

Answer 2

直感的に説明するコンピュータサイエンスは...トリッキーです。私はそれに打撃を与えるが、これのいくつかは、「十分に近い」が、理論的には厳密ではないことを行っていることを心に留めておこう。

正規言語は、有限オートマトン（DFA / NDFA）との計算と等価である機械で決定することができるものです。有限オートマトンは、状態に純粋にストレージを運営していないマシンと考えることができます。だから、あなたが見ることができる ^N B ^N それは（無限*ストレージ容量を持っている必要がありますので、と）さんとBさんの数を数えることができる機械を必要とする定期的なことはできませんそれらを比較するためにます。

比較のため、（ABC） ^N のであるの規則的な、繰り返しの数は無関係であるからである。

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

<サブ> *無限のは、ここでは関係ありませんが、私は完全を期すためにそれを言及します。 「運良く、常にちょうど十分」ストレージと考える方が簡単かもしれません。

Answer 3

おそらくウィキペディアの記事では、 通常の言語 私たちよりもうまく説明できるでしょう。ただし、試してみます。

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

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

Answer 4

言葉 regular で regular expression 英語の概念ではなく、数学的な規則の概念を指します。まさにその言葉のように prime 数学ではほとんど関係がない プライム 牛肉。

これは、より具体的な概念を指すために CS (数学の一分野) に継承されています。 http://en.wikipedia.org/wiki/レギュラー言語

Answer 5

正規表現は名前が語源で、実際には定期的にではありません。