I don't know how to prove or show the following fact.

$\quad$ $\{xx|x \in \Sigma^\ast\} $ can be accepted by a queue automaton.

If it would be possible, show by deterministic queue automaton. If not, by non-deterministic queue automaton.

If it's not that hard and if I can, please give me a hint.

  • $\begingroup$ We generally prefer that you ask only one question per post. We also prefer that you show us what progress you've made. Perhaps it is worth spending a little more time on $L_1$: can you at least find a nondeterministic queue automaton? $\endgroup$
    – D.W.
    Jan 21, 2021 at 23:23
  • $\begingroup$ @D.W. Sorry, you're right. I changed the question. Actually no, could you please give me some explanation/hint? then I try and come back $\endgroup$ Jan 21, 2021 at 23:26

1 Answer 1


Working with a queue automaton for me is intuitively equivalent to working with a circular tape.

Read the input $w$ from the automaton, and put it on the tape. Add two markers $A$ and $B$, so we obtain $Aw_1Bw_2$. Now we can one by one eat a letter after $A$ and one after $B$.

For the deterministic variant it suffices to put $B$ exactly in the middle of the input string. That position can be found using a method similar to this: How to find middle element of linked list in one pass?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.