Show that a language is regular

Question

Show that language $B$ is regular: $$B = \left\{1^ky\mid y\in \{0,1\}^*\right\} $$ $y$ contains $\ge k$ symbols $1$

So I try in following way - I'll draw DFA: What about my solution? Is it good?

Answer 1

For a fixed $k$, the concept of your solution is good, though there are a few things you can improve/correct:

$1)$ For the first $k$ states (that is state $0$ through state $k-1$), you should also define a $0$ going to some nonaccept state which then loops to itself.

$2)$ A minor correction is needed - you should label the state after the first $k$ state as $1$, not $0$ (because when you get to the green accept state $k$ with the way you currently have it we need to have seen another $(k+1)$ $1$s after the initial $k$ 1s, and we only want to require seeing another $k$ $1$s)

$3)$ Finally, there's no need to have an accept state after the green accept state $k$ - you can just loop back to that accept state because whenever you get to that point in the DFA you want to accept all strings regardless of later input.

Answer 2

Automata are not needed to answer your question. Denote by $|u|_1$ the number of occurrences of the letter $1$ in a word $u$. Setting $A = \{0,1\}^*$ and $$ L_k = \{u\in A^* \mid |u|_1 \geqslant k \} \qquad B_k = \{1^ku \mid u \in L_k \} $$ one gets immediately $$ L_k = (A^*1)^kA^* \quad \text{and} \quad B_k = 1^kL_k = 1^k(A^*1)^kA^* $$ and thus $L_k$ and $B_k$ are regular.

It is not really clear whether $k$ is fixed in your question, but even if you take any union of languages $B_k$, it will still be regular. Indeed, since $\{1\} \subseteq A^*$, one has for $k > 0$ $$ B_k = 1^k(A^*1)^kA^* \subseteq (1^{k-1}A)A^*(A^*1)^{k-1}A^* \subseteq 1^{k-1}(A^*1)^{k-1}A^* = B_{k-1} $$ and thus $$ B_0 \subseteq B_1 \subseteq B_2 \subseteq \dotsm $$ Setting, for any subset $S$ of $\mathbb{N}$, $$ B_S = \bigcup_{n \in S} B_n $$ one gets $B_S = B_s$ with $s = \min S$ and thus $B_S$ is regular.

Answer 3

Ok, So I upload correct $DFA$.