-1

question as image format

The answer can be any type of pda which satisfies the conditions

AJ Ravi
  • 1
  • Welcome to [math.se] SE. Take a [tour]. You'll find that simple "Here's the statement of my question, solve it for me" posts will be poorly received. What is better is for you to add context (with an [edit]): What you understand about the problem, what you've tried so far, etc.; something both to show you are part of the learning experience and to help us guide you to the appropriate help. You can consult this link for further guidance. – Christian E. Ramirez Dec 02 '22 at 07:24

1 Answers1

-2

Thanks for asking. So, we start by understanding the need of the question, it says that we need to design a PDA which can recognize a language that start with $w$ (which has to be a binary string as the alphabet is already defined in the question which is $[0,1]$*) and there is a separator '$c$' which separates '$w$' with its complement string that is $w^c$.

So, now let's understand this with an example string. Let $w$ be $010100110$ thus $w^c$ can be $101011001$ (we take the complement of the main string from last symbol to initial symbol because we know the top symbol of the stack would be the last symbol of the $w$ string, so our first motive would be to pop that first symbol and in order to do that we need it's complement just after that separator $c$, so if the top symbol is like 0 the next symbol after $c$ would be 1 and similarly for others too, so that will make the $w^c$ a complement string in reverse order cause other than that according to me there is no way you can accept that type of language using PDA).

In order to design a PDA which can accept this type of language we need to only keep track of two things (1) Popping condition (2) Pushing Condition. In this as the problem states we will push all the symbols till we get the input as '$c$' and the popping should be like if we get the top element in the stack as $0$ we will it pop out when we have 1 as input and vice-versa. So, our popping condition becomes $(0,1/ε)$ or $(1,0/ε)$. These are the conditions that we only consider and hence we can easily make the PDA for this.

Before seeing this try to solve it on your own

enter image description here

I hope this helps. If you have any doubt or if you think this answer need any improvement then please share your views. Thank you.

Aashutosh Agrawal
  • 1