# 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? 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. 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. Dec 11 '14 at 7:46