4
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This is it! One of my attempts even included automata for the two languages in this answer, except that I used explicit second states instead of $\emptyset$, which then obviously turned the automata into DFAs, causing the example to fail. A quick sidenote though: Shouldn't it be $L(N_{12}) = \{\epsilon\}$ instead of $\emptyset$ at the end? (Since $N_{12}$ still accepts the empty word) $\endgroup$ – Keiwan May 12 '17 at 10:01
  • $\begingroup$ Yes, indeed $L(N_{12}) = \{ \varepsilon \}$, since $(q_1,q_2)$ is an accepting state. $\endgroup$ – Hans Hüttel May 12 '17 at 11:37

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.