# Finite Automata — Determine if a set is regular

I have been at this for hours. The question is:

Prove that the language $A = \{0^kx \mid k > 0, x \in \{0,1\}^*, \text{ and } \#(0,x) \geq k\}$ is regular,

where $\#(n, x)$ denotes the number of $n$ in string $x$.

So far, I have used the pumping lemma to determine that the opposite is not regular, i.e. that if $\#(0,x) \leq k$, the language is not regular.

I have also constructed a nondeterministic finite automaton that I thought I could use to prove that this set is regular since that is generally the way to go about proving regularity. I can't really draw it, but at start state $s$, if $0$ is read in, then move to state 1 (or state $'0'$). If a $0$ is read in, either stay in state 1 or move to state 2. If a $1$ is read in, move to state 2. However, I honestly don't know what to do further.

Hint: Show that a word belongs to $A$ iff it starts at $0$ and contains at least one more $0$. That is, $A$ is accepted by the regular expression $01^*0(0+1)^*$.
• Ah ok. So in essence, we are constructing a DFA with three states $s$, $1$, and $2$ where $s$ -> $1$ if a zero is read in (and an 'inaccessible' state if a one is read in), $1$ -> $1$ if a one is read in, $1$ -> $2$ if a zero is read in, and $2$ -> $2$ if either a one or a zero is read in, with $2$ being the accept state? – tdark Dec 11 '14 at 6:56
• DFAs don't have inaccessible states, but otherwise you're right. Make sure that you know why $A$ consists exactly of these words, and that you can prove it is so. – Yuval Filmus Dec 11 '14 at 7:02
• The proof is independent of the DFA. You have to show that a word is of the form $0^k x$, where $k > 0$ and $x$ contains at least $k$ zeroes, iff it starts with $0$ and contains at least two zeroes. – Yuval Filmus Dec 11 '14 at 7:46