2
$\begingroup$

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:

enter image description here

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – BreadCrust Aug 30 at 12:35
  • $\begingroup$ That seems to be it. $\endgroup$ – Hendrik Jan Aug 30 at 18:24
2
$\begingroup$

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.

$\endgroup$

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.