4

私は試験のために改訂していますが、トピックの 1 つは正規表現です。

過去の試験問題に問題がありました

次の正規表現のうち、同等のものはどれですか? あなたの推論を説明してください。【8点】

(i) (a+b)* b (a+b)* b (a+b)*

(ii) あ・ば・ば・

(iii) a* ba* b (a+b)*

私はそれがひっかけ問題だと思うし、答えは「なし」だから

私はaabaabaabaabbaabaabaabaabbaabaabaabaabを受け入れますが、iiとiiiは受け入れません

次に、ii は 2 つの b の最大値のみを受け入れることができ、iii は最小値として 2 つの b を受け入れることができるためです。

私は正しいですか、それとも完全に間違っていますか?

講師に助けを求めて電子メールを送信しましたが、返信がなかったので、誰かが助けてくれることを願っています.

ありがとう。

4

1 に答える 1

4

iとiiiは同等です。

正規表現は両方とも「少なくとも2つのsがあるasとsの文字列」です（これは各定義から明らかであるはずです）。最初の2つの代わりにsがあるという事実は、気を散らすものです。文字列の説明を詳しく説明します。bbiiia*(a+b)*iii

  • 空の可能性のあるasの文字列（A以下のラベル）
  • 最初のb （X）
  • sの別の空の可能性のある文字列a（B）
  • 秒b（Y）
  • aそして、 sとsの単なる混合である文字列の残りの部分b（C）

あなたの例でiiiは、それと一致します。このように正規表現にラベルを付けたと想像してください（vと^は単なる矢印です）。

A  X B  Y   C
vv v vv v vvvvvv 
a* b a* b (a+b)*

次に、正規表現のどの部分が文字列の部分に対応するかをラベル付けできます。

  X  Y
  v  v
aabaabaabaabbaabaabaabaabbaabaabaabaab
^^ ^^ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
A   B            C

（@ Li-aungYipの提案も良いものです。）

于 2012-05-04T10:33:37.650 に答える