非常に単純なregex発現の説明（10）*

Question

私は非常に単純な質問をするのが気分が悪いですが、私の人生のためにこれを理解することはできません。いくつかの言語に基づいてNFAを構築する必要がありますが、私が理解できない言語はこれだけです。

L = (10)*

私はFSMに関する助けを求めているのではなく、言語が表すものについての明確化のみを求めていることに注意してください。他のほとんどの言語は、より理解しやすい方法で私に提示されました：

L = {w | w contains an even number of 0's } 

私はそれが単なる正規表現だと思っています、そして、正規表現のチートシートを熟読した後、私の唯一の推測はそれがグループと一致するということです 10 0回以上ですが、すべてが一致するため、明らかに正しくないように見えます。

どんな助けも大歓迎です。

Answer 1

意味についてのあなたの信念は基本的に正しいですが、一致するのはすべてではありません。

通常のRegexライブラリとは異なり、このような言語理論を扱っている場合、正規表現は 全体 ストリング。したがって、ε（空の文字列）は言語に、10は言語、1010は言語などです - 弦「10」が0回以上繰り返されるすべてのものはすべてです。

しかし、01はそうです いいえ 言語で;文字列は、0回以上繰り返される文字列「10」で構成されていません。 1は言語ではなく、最終0がありません。

あなたがまだこの部分をカバーしているかどうかはわかりませんが、そのregexをNFAに変換する場合（またはDFA、これには非決定論は必要ありません）、基本的にこれを取得します（わずかに単純化されています。コンバージョンアルゴリズムを正しく覚えていますが、アルゴリズムからこれまでのかなり些細な変化です）：

  1
 ┌─┐
 │ ↓
→a b
 ↑ │
 └─┘
  0

どこ a 受け入れられている状態です b ではありません。

これは、なぜそれがすべてに一致しないのかを理解するのに役立ちますか？

Answer 2

これらの文字列は言語（10）にあります*：

<empty string>
10
1010
101010
10101010
(etc.)

これらの文字列は言語ではありません（10）*：

0
1
01
11
010
01010
101
10101
(etc.)

それは助けますか？

Answer 3

これは役に立ちますか？http://xenon.stanford.edu/~xusch/regexp/analyzer.html