Welcome! Log In Create A New Profile

How can this PDA be right ( cohen pg 383 last one)

Posted by iva

Announcements		Last Post
	SoC Curricula	09/30/2017 01:08PM
	Demarcation or scoping of examinations and assessment	02/13/2017 07:59AM
	School of Computing Short Learning Programmes	11/24/2014 08:37AM
	Unisa contact information	07/28/2011 01:28PM

Forums Messages New

iva

How can this PDA be right ( cohen pg 383 last one)
April 28, 2007 08:27AM

Registered: 17 years ago
Posts: 457
Rating: 0

this 3 page example makes sense until the last PDA ( bottom of pg 383) just able concluding the proof. The PDA seems to expect a double a at the end, which is not part of L2 ? or where am i going wrong here? Just after that PDA it shows 2 strings that will be accepted by this machine (baabbb)(bba) and (baabbbbb)(a). i really can't see how that PDA can accept this . Someone please enlighten me?

Reply Quote

Peter H

Re: How can this PDA be right ( cohen pg 383 last one)
November 15, 2007 11:55AM

Registered: 18 years ago
Posts: 69
Rating: 0

Well, yes it does have have the words ending in aa in it. That's why it's wrong. See the last sentence of that page. "does it work in all cases?"

So if you have to prove that PDA_3 accepts L_1L_2 you'll get the one half of the proof right. That being that it does accept the language. But the other half, excluding all other words have counterexamples . So it's not the case.

Looked at this very fast, so please someone correct me if you see a flaw.