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?

$\endgroup$
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.

$\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.