I am a bit confused about the notation that is used in the book I am reading.
Let's say I have such a regular expression
(a + b)*(aa + bb)(a + b)*
So starting from the first one, I will pick either a or b or none then I have to add aa or bb then again I will pick either a or b or none.
so some of the words below belong to this regular expression: aaa aaab bba
but for example abaa is not accepted.
However, the author gives a finite automata like that:
The author says the regular expression belong to this finite automata is
(a + b)*(aa + bb)(a + b)*
Same like above. But based on the graph, abaa can be achieved. However, I cannot produce abaa with the regular expression above. What am I doing wrong exactly?
The confusion comes in interpreting the Kleene star. $(a+b)^\star$ means an arbitrary number of $(a+b)$'s. Hence, this is an arbitrary string, of length $0$ or longer, containing either $a$'s or $b$'s in any order.
To get $abaa$, interpret the expression first as $(a+b)(a+b)(aa+bb)$, where we take the first $(a+b)^\star$ twice and the second $(a+b)^\star$ zero times. Then, interpret this as $abaa$.