W (WR) * правильный?

Question

L = {W (WR) *}, w = (a + b) *, где WR является обратным по отношению к W. Является ли этот язык регулярным?

По моему мнению, это не должно быть регулярным, так как может быть случай, когда мы можем иметь W (WR), который не является регулярным, но в книге правильный ответ.

Может ли это объяснить это?

Answer 1

Трюк - это звезда. (WR) * включает пустое слово. Таким образом, L включает в себя все слова W, связанные с пустым словом, т. Е. Все слова W. И множество всех слов, конечно, является регулярным.

Для W (WR)^+ все будет выглядеть совсем по-другому. Но со звездой все обратные являются лишь некоторыми из многих, многих слов языка.