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