# DPDA for $\{1^ky \mid \text{$y\in \{0,1\}^*$with$|y|_1 \le k$and$k \in \mathbb N: k\ge1$}\}$

I need some help with the following task:

I have to construct a DPDA for $$\{1^ky \mid \text{y\in \{0,1\}^* with |y|_1 \le k and k \in \mathbb N: k\ge1}\}$$.

How can I recognize that the new substring $$y$$ begins? For example: $$w=zy$$, where $$z = 1111$$ and $$y = 1001$$.

This is what I have so far:

In order to verify whether the string is of the form $$1^ky$$ with $$y\in \{0,1\}^*$$ and $$|y|_1\le k$$ you want to determine whether a symbol $$1$$ in the prefix belongs to the $$1^k$$ part, or starts $$y$$.

Now imagine $$1^k \cdot 1y$$ is of the correct form, i.e., $$|1y|_1 \le k$$, then certainly $$1^{k+1}\cdot y$$ is also correct, as $$|y|_1< |1y|_1 \le k < (k+1)$$.

So, keep reading $$1$$'s while possible.

• Ahh I see. So I have to push the first $1's$ until the first $0$ is under the head. From that point on I have to pop $1's$ until the stack is empty and go in an accept state iff the string w is empty. Otherwise I do not accept w. Is this correct? Aug 30 '19 at 12:35
• That seems to be it. Aug 30 '19 at 18:24

It is clear $$y$$ starts with $$0$$; so all you have to do is to push $$1$$ on the stack as long as there is no $$0$$, afterwards delete a $$1$$ from the stack for each $$1$$ in the input. This will jam if there are too many $$1$$s in $$y$$, you can accept by final state if you reach the end of the input.