How to build a Finite Automata by combining two regular expressions?

Question

Good day,
I was given the below question that relates to Kleene's Theorem (RE to FA):

Question
Consider the following FA's with the corresponding regular expressions $r_1$ and $r_2$

$r_1$:

$r_2$:

Build an FA for the regular expression $r_1r_2$ by applying Kleene's theorem (do not formulate any regular expression)

Note: I only need to create a table with the z states. I know how to do this but I get stuck when the new z state is a starting state in one FA but not in the other one. Let me give you an example:

Is z3 also a starting state (-z3), because it circles back to itself, in $r_1$, if the input in -z1 is a b or not? Is there only one starting state in the new FA for $r_1r_2$?

This is the only thing I get stuck on. I need to know this if I want to finish the table and draw the new FA for $r_1r_2$.

Thank you.

Answer 1

I am going to presume the following interpretations:

1. $+$ denotes an accepting state (end here, the string is accepted)
2. $-$ denotes the unique starting state (you start here)
3. $r_1r_2$ asks for the alternation of the regular expressions, typically denoted $r_1|r_2$

---

For the specific special case of two DFA inputs to $r_1|r_2$, you can simulate both paths at once in parallel.

1. Keep track of all found possibilities of states (X,Y) where X is a state of $r_1$ and Y is a state of $r_2$
2. The only initial state is (initial state of $r_1$, initial state of $r_2$)
3. Whenever you are in state (X,Y) seeing input letter $z$, go to (wherever X goes to on input $z$, wherever Y goes to on input $z$).
4. All states (X,Y) such that either X accepts in $r_1$ or Y accepts in $r_2$ will accept for $r_1|r_2$.

---

These general constructions work for any input, including NFAs:

To construct the concatenation $r_1r_2$, that is $\left\{xy\mid x\in r_1,y\in r_2\right\}$, simply do the following:

1. Repeat the entire DFA (or NFA, it doesn't matter) representation of both $r_1$ and $r_2$ as states and transitions.
2. Only the initial (-) state(s) of $r_1$ are initial states of $r_1r_2$.
3. Only the final (+) state(s) of $r_2$ are final states of $r_1r_2$.
4. Add $\epsilon$-transitions (those that consume zero input) connecting each final state of $r_1$ to each initial state of $r_2$.
5. Convert the NFA to DFA if necessary.

To construct the alternation $r_1|r_2$, that is $r_1\cup r_2$, simply do the following:

1. Repeat the entire DFA/NFA representation of both $r_1$ and $r_2$ as states and transitions.
2. All initial (-) and final (+) states of $r_1$ and $r_2 $ are simply initial/final states of $r_1|r_2$.
3. If you need a unique start state, create one, and add $\epsilon$-transitions connecting the start state to each initial state of both $r_1$ and $r_2$.
4. Convert the NFA to DFA if necessary.

You can consider all transitions that lead to state X to be copied (keeping the original) to lead to wherever X goes to under $\epsilon$-transitions.

Nothing will avoid having multiple transitions - this is, after all, a real use of nondeterminism. The $\epsilon$-transitions represent "guessing", either where the end of the first substring part is (for $r_1r_2$) or which type of string to match to begin with (for $r_1|r_2$).

The NFA$\rightarrow$DFA conversion of course can lead to exponential blowup (the new set of states is the powerset, i.e. set of all subsets, of the original states). Typically the number of reachable subset-states is very limited.