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
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityI 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.