0
$\begingroup$

Prompt: if $N$ is NFA that has at most one choice of state for any state and input symbol, then the DFA constructed from $N$ by subset construction has exactly the state and transitions of $N$ plus transitions to new dead state whenever $N$ is missing transition for given state and input symbol. Prove this contention.

I get this intuitively and I wrote out a proof, but I think it may not be formal enough to be an actual proof.

  1. Prove that DFA has all the same states of $N$ plus a new dead state

$\delta(q,a)$ never has size greater than one. This means on reading input symbol $a$ from a state $q \in Q$, the DFA transitions to a single state or it dies. In other words, $\delta_N(q,x) = \{p_1\} | \emptyset$, where $q, p_1 \in Q_N$ This means $Q_N$ consists of singleton states.

Subset construction gives us $Q_D$ as states of DFA constructed from N, which is equal to $P(Q_N)$. However, as $\delta(q,a)$ never has size greater than one - or it only goes to a single state or it dies - the only subsets $S$ of $Q_N$ accessible by the DFA are the singleton states of $P(Q_N)$, which is also equal to $Q_N$. In this way, $Q_D = Q_N + z$, where $z$ is new dead state.

  1. Prove that DFA has all same transitions of N plus transitions to dead state whenever N is missing transition for given state and input symbol

Subset construction tells us that

for each set $S \subseteq Q_N$

$\delta_D(S,a) = \cup_{i}^{k} \delta_N(p,a)$

Pt.1 showed that $S = \{p\}$, so we don't need to take the union of each $p$ in $S$ because there is only one state.Therefore we can say $$\delta_D({p}, a) = \delta_N(p,a)$$

In the case then that $\delta_N(p,a) = \emptyset$, then we add a transition to the new dead state. Therefore the union of all the transitions of the DFA equals the union of all the transitions of $N$ plus the new transitions to the dead state.

$\endgroup$
  • $\begingroup$ What exactly is your question? This is a question-and-answer site, so we require you to articulate a specific question that you want answered (e.g., a question about some aspect of your question). Do you have a specific doubt in your proof? $\endgroup$ – D.W. Mar 15 '18 at 6:26
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W. Mar 15 '18 at 6:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.