Регулярные выражения. Это одни и те же регулярные выражения?

Question

У меня есть два вопроса. Являются ли эти регулярные выражения одинаковыми?

(1) б * (AB *) * и (б * а) * б *

(2) б * (AAAB *) * и (б * ааа) * B *

Я чувствую, что они оба создают язык, в котором есть палиндром мира. Это правильно? В первом случае оба a должны и b равны нулю или неограниченны. Второй - тот же. строка aaa является обязательной для обоих, а b - нулевой или неограниченной.

Я прав?

Answer 1

В обоих случаях два регулярных выражения не совпадают (это разные регулярные выражения), но они do описывают один и тот же язык. Итак, ответ на оба вопроса (из ваших упражнений?) - «да».

В первом случае регулярные выражения описывают язык любой строки из a х и b лет. Во втором случае вы получаете язык, где все a происходит в тройках, в виде комбинации aaa. Этот первый язык также описывается регулярным выражением (a|b)* (или (a + b)*, или (a U b)*, я не знаю, какую нотацию использует ваша книга), а второй язык также описывается регулярным выражением (aaa|b)*.

В обоих случаях языки остаются неизменными, если вы меняете элементы, и поэтому, если вы отмените регулярные выражения, которые их описывают, они останутся неизменными.

Palindromes - слова, которые сами остаются неизменными, если вы их отменили. Но на обоих языках есть элементы, которые являются не palindromes, например, слово aaab, потому что aaab! = baaa. Поэтому говорить о палиндромах не является правильным аргументом здесь.