文字列一致の正規表現評価

Question

私はRobert Sedgwickの本によるアルゴリズムの正規表現を読んでいます。ここで

A* | (A*BA*BA*)* 

以下の正規表現の言及のためにここで

著者はマッチを言及は、以下のとおりです。AAA、BBAABB、およびBABAAA。 は上記の正規表現と一致しませんABA BBB BABBAAAです。

私の質問は、どのようにBBAABBがBABAAAとマッチングしているかと同じ方法で一致していることです。親切に説明してください。

一般的に私は|正規表現内の*演算子。 以下の例では、もし私たちが+ 1を持っていれば、セットでbをどれだけ得ることができるかは、少なくとも1つaでなければならないと言います。

(a+b)* = (λ, a, b, aa, ab, ba, bb, aaa, ...) 

Answer 1

*と+の間に1つの違いがあります。その後、*を置くキャラクターは、繰り返しはありません。しかし、+のケースでは、最小1回の繰り返しが可能です。 はA* | (A*BA*BA*)*において、BBAABBは、次の理由のため有効であり、それは(A*BA*BA*)*BA*ためA*

1 B用パターン

1. 開始時無AとBA*なしA
2. 1 B 2
に従ってれます
3. *(A*BA*BA*)*の末尾にパターンが繰り返されることが示されています。したがって、2回目の繰り返しは有効なBBです。

これらは、BBAABBが有効なポイントです。