When does the product automaton of two NFAs A and B not decide L(A) U L(B)?

Question

We are given the following task:

Let $\mathcal{A} = {}(Q_A,\Sigma, \delta_A, s_A, F_A)$ and $\mathcal{B} = {}(Q_B,\Sigma, \delta_B, s_B, F_B)$ be two NFAs and let their product automaton be defined as:

$\mathcal{A} \times \mathcal{B} = {}(Q_A \times Q_B,\Sigma, \delta, (s_A,s_B), F)$ with

$\delta = {}\{ ((p,q),\sigma,(p',q')) \mid (p,\sigma,p') \in \delta_A, (q,\sigma,q') \in \delta_B \}$ and

$F= {}(Q_A \times F_B) \space \cup \space (F_A \times Q_B)$

(So the accepting (combined) states are the ones where at least one of the two individual states of $\mathcal{A}$ or $\mathcal{B}$ is accepting.)

Give an example for two NFAs $\mathcal{A}$ and $\mathcal{B}$ so that their product automaton $\mathcal{A} \times \mathcal{B}$ does not decide the language $L(\mathcal{A}) \space \cup \space L(\mathcal{B})$.

Now the one thing that is by far confusing me the most (and what I want to focus on in this question) is the following tip that is given as well:

Tip: There is an example in which $\mathcal{A}$ only has one state.

I can't see how that could be possible, with the following reasoning:

If $\mathcal{A}$ only has one state - let's call it $q$ - this means two things:

1. $q$ is either accepting or it is not accepting
2. All of the transitions of $\mathcal{A}$ start at and directly lead back to $q$.

Based on 1. we have two cases.

Let's first consider the case that $q$ is accepting ($q \in F_\mathcal{A}$). Because of 2. it follows that $\mathcal{A}$ accepts every word $w \in \Sigma ^*$ (so $L(\mathcal{A}) = \{w \in \Sigma^*\}$).

Let $\mathcal{B}$ be an arbitrary NFA. Based on the definition of $F$ and the fact that $q$ is accepting it is clear that all of the states of $\mathcal{A} \times \mathcal{B}$ will be accepting as well, which implies that the product automaton also accepts every $w \in \Sigma ^*$.

This means that $\space L(\mathcal{A} \times \mathcal{B}) = \{w \in \Sigma^*\} = L(\mathcal{A}) \space \cup \space L(\mathcal{B})$.

Now let $q$ be non-accepting ($q \notin F_\mathcal{A})$. Again, based on the definition of $F$ we can see that the accepting states of $\mathcal{A} \times \mathcal{B}$ are going exactly correspond to the accepting states of $\mathcal{B}$.

Point 2 implies that the transitions of $\mathcal{A}$ will "not have any impact on the transitions of $\mathcal{A} \times \mathcal{B}$", by which I mean that the product automaton is going to have the same transitions as $\mathcal{B}$ and therefore be isomorphic to $\mathcal{B}$, which again results in

$L(\mathcal{A} \times \mathcal{B}) = L(\mathcal{B}) = L(\mathcal{B}) \space \cup \space \varnothing = L(\mathcal{B}) \space \cup \space L(\mathcal{A})$

(since $\mathcal{A}$ doesn't accept any input, which means $L(\mathcal{A}) = \varnothing$)

This proof is trying to show that if $\mathcal{A}$ only has one state, then $\mathcal{A} \times \mathcal{B}$ will always decide $L(\mathcal{B}) \space \cup \space L(\mathcal{A})$.

Obviously, there has to be a logic fault in my thinking and in the proof above somewhere, which I can't seem to be able to figure out, so I'd really appreciate if anyone could point out what I'm missing.

Answer 1

The culprit is the fact that, in the presence of nondeterminism, automata need not have transitions to other states for the same input symbols.

Consider two NFA over the input alphabet $\{a,b\}$:

$$N_1 = (\{q_1\},\{a,b\},q_1,\delta_1,\{q_1\})$$

where $\delta_{1}(q_1,a) = \{ q_1 \}$ and $\delta_{1}(q_1,b) = \emptyset$

and

$$N_1 = (\{q_2\},\{a,b\},q_2,\delta_2,\{q_2\})$$

where $\delta_{2}(q_2,a) = \emptyset$ and $\delta_{2}(q_2,b) = \{ q_2 \}$

– that is, each of these automata has a single state, which is accepting, and a single transition, which is a loop on $a$ or $b$, respectively.

Clearly, $L(N_1)= \{ a^n \mid n \geq 0 \}$ and $L(N_2)= \{ b^n \mid n \geq 0 \}$. But the product construction will give us an automaton

$$N_{12} = (\{ (q_1,q_2 \}, \{ a,b \}, (q_1,q_2), \delta_{12}, \{ (q_1,q_2)\})$$

where $\delta_{12}((q_1,q_2),a) = \emptyset$ and $\delta_{12}((q_1,q_2),b) = \emptyset$, since there is no symbol $x$ such that both $N_1$ and $N_2$ admit an $x$-transition from their sole state.

Therefore $L(N_{12}) = \{ \varepsilon \} \neq L(N_1) \cup L(N_2)$.