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

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:

• $q$ is either accepting or it is not accepting

• 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 ($

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

StackExchange Computer Science Q#75264, answer score: 6