# Create a PDA that accepts the following language

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.

• 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 – Haseeb Hassan Asif Nov 12 '20 at 4:46
• $u$ can be any string made up of $a$'s and $b$'s – 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 :

• 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? – Fraser Nov 12 '20 at 14:59
• 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 – Anazz Nov 12 '20 at 15:47