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
|
$\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 '20 at 13:48
-
$\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