I am solving some example exercises in preparation of a Computational Theory examination.
In Exercise 2, I am tasked with building an NFA and DFA of the regular expression: $(b|bba)^*a$
My question is: Can I simplify $b|bba$ inside the parentheses to $bba$? Are they indeed equivalent or will I be breaking some generality?
I am asking this since it is going to be easier for me to construct the automata after the simplification.
Usually, concatenation is assumed to bind stronger than alternative, so you have $b \mid (bba)$, not $(b \mid b)ba$.
Then no, you can't drop "$b\ \mid$" since $b^+a \subseteq \mathcal{L}\bigl((b \mid bba)^*a\bigr)$ but $b^+a \cap \mathcal{L}\bigl((bba)^*a\bigr) = \emptyset$.
For what it's worth, $\mathcal{L}(b \mid b) = \{b \} = \mathcal{L}(b)$, so that simplification would be valid. More generally, if $\mathcal{L}(r_1) \subseteq \mathcal{L}(r_2)$, then $\mathcal{L}(r_1 \mid r_2) = \mathcal{L}(r_2)$.
