2
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\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$
    – Mikey Freeman
    Jan 21, 2021 at 23:26

1 Answer 1

Reset to default
1
$\begingroup$

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?

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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