I have a homework where I have to construct two way deterministic pushdown automaton that accepts this language:

{ww | w ∈ {a, b}*}

Does anyone have any idea? Thanks a lot


Here are the two basic ideas.

(1) After checking that the input length is even, move to the middle position of the input. The trick to find that position uses the stack in a similar way that we recognize the language $\{\;a^{2n}b^n \mid n \ge 0\;\}$.

(2) Then check that the two halves are equal. Here the stack is used in a similar way that one recognizes the language $\{\; ww^R \mid w\in\{a,b\}^*\;\}$, except that the head does not move forward in both cases.

  • $\begingroup$ No, I can't find the middle of the input $\endgroup$ Dec 2 '20 at 13:52
  • $\begingroup$ But how do I know the number of items to pop to return to the middle $\endgroup$ Dec 2 '20 at 14:14
  • $\begingroup$ I would push nothing every second 'a' and then pop when 'b' occurs $\endgroup$ Dec 2 '20 at 14:29
  • $\begingroup$ In better words, I would push 'aa' and just replace 'a' with 'a' every second 'a' $\endgroup$ Dec 2 '20 at 14:52

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.