0
$\begingroup$

I have to construct PDA for ${ \{0^m1^n0^{2n} | n>0\}}$

So my idea is to (informally) not pushing anything into the stack while having 0s at first, then when automata start accepting 1s it should push X onto the stack twice on every 1 and then when start accepting 0s it should pop X once every time until stack will be empty.

Is my understanding correct? If not, how should I proceed?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Yes, your understanding is correct. You may need a bit more mechanism to ensure there is at least one 1 after the initial 0's.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.