2
$\begingroup$

I'm assigned to build a kPDA with 2 stacks that handles {w#w, where w is a string of (0,1)*}. I understand the # delineates the two strings, but I'm unsure of the logic when popping off stacks with epsilon. I asked my professor, verbally, if this works and he told me no, but I can't think of any other way.

enter image description here

EDIT: Here is the full machine:

enter image description here

Improve this question
$\endgroup$
4
  • $\begingroup$ An idea: First, put any symbols of the string in stack1, until you reach '#'. Stack1 will contain the reverse of the current input. Move the data from stack1 to stack2 to "unreverse" the reversed content of stack1. Now, continue processing the input and for any symbol in the input, if it matches with the top of stack2 then pop it from stack 2. If it doesn't match, you should reject. $\endgroup$ – frabala Mar 26 '19 at 12:12
  • $\begingroup$ Also, the image is not clear to me. It's cropped. I can only see two states ($q_3$ and $q_4$, none of which is accepting). $\endgroup$ – frabala Mar 26 '19 at 13:57
  • $\begingroup$ Hey @frabala thanks for the comment! I didn't want to post my whole machine to get in any scholarly trouble, but I'll update it with the whole machine as the assignment has already been submitted. $\endgroup$ – bangbangpowpow Mar 26 '19 at 19:42
  • $\begingroup$ I don't see why the provided 2PDA doesn't do the job... It isn't minimal (it could have less states) but it seems correct to me. It puts the first part of the input string in stack1. After reading the # symbol, it puts the rest of the string in stack2. Lastly, it pops simultaneously the tops of stacks 1 and 2 (making sure that those top symbols are the same), until it reaches simultaneously the dollar sign. If your professor has explained what is wrong with your 2PDA, I would appreciate it if you could let us know with a comment here. $\endgroup$ – frabala Mar 28 '19 at 13:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.