We have this language: $$ L = \{𝑥𝑥^r|𝑥∈Σ^∗\} $$

We want to show that it can be accepted by QA.

  1. consider a letter like #, before anything we push it to the queue.
  2. using this additional letter, we push every letter we get such that it would be the first letter of the string inside the queue (i.e. letter after #)
  3. then (using Lambda Transition), we remove # from the queue, and we pop the letters come from input one by one out of queue. E.g. we get abccba from the input, we want to get string: abc#E in the queue, then remove # to reach abcE. then from this point when we get c from the input, we remove c from the queue's head.

Is this approach correct? Could you show me the queue automaton of it?

Thanks in advance.


Your Answer

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

Browse other questions tagged or ask your own question.