3
$\begingroup$

The truth is that my teacher gave us a homework, and I wanted to ask you if I did this right.

What I have to do is answer the following questions given the following NFA.

NFA

  1. Why is this an NFA?
  2. What language describes the NFA? Describe in your words and indicate the corresponding regular expression
  3. Transform it into a DFA and indicate their dead, initial and final states.

So my answers are...

  1. Because it holds that: $\delta(q_1, \epsilon) = q_{14}, \text{with } q_1 \neq q_{14} (\text{in a DFA is always true that $\delta(q, \epsilon) = q$})$ and $\delta(q_2, \epsilon) = q_3, \delta(q_2, \epsilon) = q_7, \text{with } q_3 \neq q_7 (\text{in a DFA if $\delta(q, a) = q_1$ and $\delta(q, a) = q_2, \text{then is always true that } q_1 = q_2$})$.
  2. The regular expression is $1(11|0^*)^*$, that is, the set of strings containing $0$s and $1$s starting with a $1$, having an odd number of $1$s and wherein each $1$ after the first, will be accompanied by at least another $1$.
  3. The DFA I got was this.

enter image description here

Initial state: A, Final states: C, D, E and Dead state: B.

I did it well?

$\endgroup$
  • $\begingroup$ I would give that answer full marks, although I do notice that you can merge states D and F of your DFA. (In fact, it's possible to write a DFA with only 4 states. I think once you merge D and F it will be clear that you can also merge them with C.) $\endgroup$ – MJD Apr 5 '15 at 4:10
  • $\begingroup$ Thanks for the reply, with regard to what you say that I can merge D, F and C, is there a way to transform the NFA to DFA with fewer states algorithmically?, or is it by guess?, because of the way I did (applying e-closure to the states to the initial state, etc...) it resulted in exactly the DFA that I show on the last picture. $\endgroup$ – OiciTrap Apr 5 '15 at 4:35
  • 1
    $\begingroup$ You are looking for the Myhill-Nerode theorem. $\endgroup$ – MJD Apr 5 '15 at 4:41
  • $\begingroup$ @MJD The minimal DFA has 3 states and even just 2 states if you allow incomplete automata. $\endgroup$ – J.-E. Pin Apr 5 '15 at 10:40
4
$\begingroup$
  1. A DFA has no $\epsilon$-transitions, so this is not a DFA. I would rather called your automaton a nondeterministic finite automaton with $\varepsilon$-moves.

  2. Your regular expression $1(11 \cup 0^*)^*$ is correct. Your informal description is almost correct: you should just modify your sentence

each $1$ after the first, will be accompanied by at least another $1$

as follows:

if one counts only the $1$, every $1$ in even position is followed by a $1$.

The problem with your formulation occurs for instance for the word $1110$: this word is in the language, however the third $1$ is not followed by a $1$.

  1. Hint. The minimal automaton has actually 3 states.

  2. For the question in your comment see the answer to this question.

$\endgroup$
  • $\begingroup$ One might also mention that it fails to be a DFA because it’s missing some of the required transitions, e.g., a $0$ transition from $q_0$. $\endgroup$ – Brian M. Scott Apr 5 '15 at 17:19
  • $\begingroup$ @brian-m-scott Some authors do not require this condition and refer to complete deterministic automata for a DFA with this property. See in particular, Eilenberg's definition p. 30 in his book Automata, Languages and Machines, Vol A, Academic Press, 1974. $\endgroup$ – J.-E. Pin Apr 5 '15 at 18:04

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.