正規表現 - それらは同じ正規表現ですか？

Question

私には2つの質問があります。それらの正規表現は同じですか？

（1）のb *（AB *）*および（b * A）* B *

（2）のb *（AAABの*）*および（b *表AAA）* B *

私は彼らが両方とも世界の回文を持つ言語を作成するように感じる。そうですか？最初のものでは、aは必須であり、bはゼロまたは無制限です。 2つ目は同じです。文字列aaaは両方とも必須であり、bはゼロまたは無制限です。

私は正しいですか？

Answer 1

どちらの場合でも、2つの正規表現は同じではありません（異なる正規表現です）が、はと同じ言語を記述します。だから両方の質問（あなたの演習からの答え）は "はい"です。

正規表現では、の文字列aとbの文字列が記述されています。 2番目のケースでは、すべてのaがトリプルで出現する言語を、aaaとして取得します。この最初の言語は正規表現(a|b)*（または(a + b)*または(a U b)*、私はあなたの本が使用する表記を知らない）で記述され、第2言語も正規表現(aaa|b)*で記述されます。

どちらの場合も、要素を逆にすると言語は同じになります。そのため、それらを記述する正規表現を逆にすると、同じままになります。

パインドームは、自身のような言葉です。しかし、両方の言語は、aaab！= baaaのように、aaabという単語のように、でない要素がでない要素を持っています。それでパリンドロームについて話すことは、ここでの正しい議論ではありません。