# How can a deterministic or non-deterministic automaton accept the language of square strings?

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.

• 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?
– D.W.
Jan 21, 2021 at 23:23
• @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 Jan 21, 2021 at 23:26

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?