How can we create a push down automata for a language L = W W^R

Thread Starter

zulfi100

Joined Jun 7, 2012
656
Hi,
Let w=abb then w^R (i.e. reverse of w ) = bba.

The problem is that how can we recognize the middle point of abbbba. Left part = abb and right part = bba. Both the parts have same symbols. So how will we know that the left part has ended and the right part has started? We can't use a sentinel while reading the left part because we don't know when the left part would end. If we know we can put a special character to differentiate between the two parts.

Kindly guide me how to solve this problem.

Zulfi.
 

Thread Starter

zulfi100

Joined Jun 7, 2012
656
Go back and review how nondeterministic finite automatons work.
Hi,
Thanks for your reply.

I have already read non-deterministic automata. Can you please provide me a link of the document which you specifically want me to read?

Zulfi.
 

WBahn

Joined Mar 31, 2012
29,979
Hi,
Thanks for your reply.

I have already read non-deterministic automata. Can you please provide me a link of the document which you specifically want me to read?

Zulfi.
You may have "read" about non-deterministic automata, but you clearly did not comprehend them or how they work. There are LOTS of resources available to help you understand them. There is no reason to believe that whatever material I give you a link to will help you any more than what you already have if all you are going to do is "read" it.
 

Thread Starter

zulfi100

Joined Jun 7, 2012
656
You may have "read" about non-deterministic automata, but you clearly did not comprehend them or how they work. There are LOTS of resources available to help you understand them. There is no reason to believe that whatever material I give you a link to will help you any more than what you already have if all you are going to do is "read" it.
I think you are right, we need nfa. But particularly lambda transition. I found a solution for it. But I don't know why we need lambda transition in this case. I am able to understand the rest of the stuff.

Somebody please guide.

I have uploaded the solution but it is using different notations then what we have in the book whose pages I sent in an earlier post.

Zulfi.ww_reverse.jpg
 
Top