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
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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.
answered Dec 2, 2020 at 13:48
-
$\begingroup$ No, I can't find the middle of the input $\endgroup$ Dec 2, 2020 at 13:52
-
$\begingroup$ But how do I know the number of items to pop to return to the middle $\endgroup$ Dec 2, 2020 at 14:14
-
$\begingroup$ I would push nothing every second 'a' and then pop when 'b' occurs $\endgroup$ Dec 2, 2020 at 14:29
-
$\begingroup$ In better words, I would push 'aa' and just replace 'a' with 'a' every second 'a' $\endgroup$ Dec 2, 2020 at 14:52