正則表達式 - 它們是相同的正則表達式？

Question

我有兩個問題。這些正則表達式是相同的嗎？

（1）的b *（AB *）*和（b * a）個* b *表

（2）的b *（AAAB *）*和（b * AAA）* b *表

我覺得他們都創造了具有世界迴文的語言。是對的嗎？在第一個中，a和b都是零或無限。第二個是一樣的。字符串aaa在兩者中都是必須的，而b是零或無限的。

我對不對？

Answer 1

在這兩種情況下，兩個正則表達式都不相同（它們是不同的正則表達式），但它們都是do描述的是相同的語言。所以這兩個問題的答案（從你的練習？）是「是」。

在第一種情況下，正則表達式描述了的任何字符串的a和b的語言。在第二種情況下，您將獲得所有a以三倍出現的語言，如組合aaa。第一種語言也用正則表達式(a|b)*（或(a + b)*或(a U b)*，我不知道您的書使用什麼表示法）來描述，第二種語言也用正則表達式(aaa|b)*來描述。

在這兩種情況下，如果反轉元素，語言都保持不變，因此，如果反轉描述它們的正則表達式，它們也保持不變。

迴文是自己保持不變，如果你反轉它們。但是這兩種語言的元素都是而不是迴文，例如aaab這個詞，因爲aaab！= baaa。所以在這裏討論迴文不是正確的論點。