2
$\begingroup$

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.

|cite|improve this question
$\endgroup$
2
$\begingroup$

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)^*$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – tdark Dec 11 '14 at 6:56
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Dec 11 '14 at 7:02
  • $\begingroup$ Does the proof of why A consists exactly of these words involve the DFA's delta and delta-hat functions? $\endgroup$ – tdark Dec 11 '14 at 7:19
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Dec 11 '14 at 7:46
  • $\begingroup$ Ok. So basically I have down this: suppose for w in A that w does not begin with a zero and contain at least two 0s. Thus, we have three cases: w begins with a 1 and #(0,w) >= 2, w begins with a 1 and #(0, w) < 2, and w begins with a 0 and #(0,w) < 2. The first two cases are trivially false, as A is defined as beginning with a zero. For the third case, with w begins with a zero, k = 1 at this point in time. Since k=1, x must have, by definition, at least one zero, bringing the total number of zeroes to at least 2, thereby invalidating the case. Thus, the #(0,w) >= 2, w begins with a zero... $\endgroup$ – tdark Dec 11 '14 at 8:14

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.