# this language and acceptance by queue automaton

I don't know how to prove or show that:

$$L_1 = \{xx|x \in \Sigma^\ast\}$$ (that can be accepted by 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. Thanks in advance.

• 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 '21 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 '21 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?