I need to create a PDA that accepts by empty stack and accepts the language formed by strings over the alphabet $\{a, b\}$ of the form: $uw$, where $w$ is the string $u$ reversed and doubled. So, for example, if $u=ab$ then $w=bbaa$ (the $ab$ is reversed then its characters are doubled).

Examples of strings in the language: $\epsilon$, $aaa$, $baaabb$, $abbbbbbaa$, etc.

I'm really struggling with setting up a PDA that satisfies the criteria. Any help is appreciated.

  • 1
    $\begingroup$ Please tell if there are any conditions on string u and w... it would be better if you define the language than give an example of it for a comprehensive answer $\endgroup$ – Haseeb Hassan Asif Nov 12 '20 at 4:46
  • $\begingroup$ $u$ can be any string made up of $a$'s and $b$'s $\endgroup$ – Fraser Nov 12 '20 at 14:39

The PDA operates as follows :

  1. Push the symbols you read to the stack

  2. Non-deterministically guess when u ends and w starts

  3. Now for the rest of the string , we consider 2 symbols by 2 symbols , if the 2 symbols are not the same reject , if the 2 symbols are the same , compare them to top of stack , if they are not the same symbol reject , if they are the same pop the stack

  4. After reading the entire input , if the stack is empty accept , else reject

Ex : s = ab bbaa , we push a,b to stack , then we guess u ends and w starts , now we read b , then b , both are same symbol , we look at top of stack we have b we pop the b , now the stack has a , and we will read aa , repeat the above again and we accept

If you get how it works , you may want to try to sketch the PDA

Here is a sketch of the PDA to check your answer :

  • $\begingroup$ Thank you! Your explanation is very helpful. I'm still struggling to put it all together but I'm getting there. Your use of the symbol #, I'm assuming that's equivalent to the use of $Z_{0}$ used in my textbook to denote the empty stack? $\endgroup$ – Fraser Nov 12 '20 at 14:59
  • $\begingroup$ Yes , some books use Z0 and some use $$ , but you should remember that any special symbol can be used to do this check , by special we mean that it is in Γ but not in Σ , and is only used to do the check (these conditions guarantee that no problem occurs) , however Z0 is preferable since some languages contain # or $ , so in this PDA feel free to replace # by Z0 , if you have any other questions please feel free to ask $\endgroup$ – Anazz Nov 12 '20 at 15:47

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.