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)$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.