NFA to DFA and Regular Expression

Question

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.

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.

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

I did it well?

Answer 1

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

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

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