How to find errors in the definition of DFA which expands upon another DFA?

52 Views Asked by At

Let $A=(\{0,1,2\}, Q,q_0,F,\delta)$. $A$ is deterministic finite automaton (DFA). We want to build a new DFA, $B$ off $A$ which would receive $L(A)\cap\{0,1\}^+$ as follows: $$ B=(\{0,1,2\}, Q\cup\{p\}, q_0,F\cap(Q-\{q_0\}), \mu)\\ \forall \sigma\in \{0,1\}, q\in Q:\mu(q,\sigma)=\delta(q,\sigma)\\ \forall q\in Q:\mu(q,2)=p\\ \forall \sigma \in \{0,1,2\}:\mu(p,\sigma)=p $$ Find two mistakes in the definition of $B$.

I think the first mistake is that some state $q$ may have a transition with $2$ and with $0$ or $1$. In that case the next state is not clearly defined in $B$ because on the one hand $\mu(q,2)=p$ while at the same time $\mu(q,1)=\delta(q, 1)\neq p$ because $p\notin Q$. So $B$ is non-deterministic.

I think the second mistake is that the set of accepting states in $B$ doesn't include $q_0$. Suppose the transition function for $A$ is something like this:

enter image description here

So $\delta(q,0)=\delta(q,1)=\delta(q,2)=q_0$. But $B$ doesn't include $q_0$ so it won't have any accepting states.

1

There are 1 best solutions below

0
On BEST ANSWER

As proposed, the automaton $B$ is a DFA, so there is no mistake on this side. However, it does not recognise the language $L(A)\cap\{0,1\}^+$. Indeed, if you take the language $\{0,1,2\}^*$, its minimal DFA is the one you found. Therefore $L(A)\cap\{0,1\}^+ = \{0,1\}^+$, considered as a language on the alphabet $\{0,1,2\}$, and its minimal automaton has 3 states. Thus $B$, which has 2 states in this case, cannot recognise $\{0,1\}^+$.

The correct construction for $B$ is the following. Let $$ B=(\{0,1,2\}, Q\cup\{p,r\}, r, F, \mu) $$ where the transition function $\mu$ is defined as follows \begin{align} \mu(r,0) &= \delta(q_0,0) &\quad \mu(r,1) &= \delta(q_0,1) &\quad \mu(r,2) &= p \\ \text{If $q \in Q$ then}\quad \mu(q,0) &= \delta(q,0) &\quad \mu(q,1) &= \delta(q,1) &\quad \mu(q,2) &= p\\ \mu(p,0) &= p &\quad \mu(p,1) &= p &\quad \mu(p,2) &= p \end{align} Intuitively, the new initial state $r$ is introduced just to avoid to accept the empty word and every transition labeled by $2$ leads to the sink state $p$.

I let you argue on the number of errors in the proposed automaton $B$.