Welcome! Log In Create A New Profile

Advanced

Random Question

Posted by BlaXpydo 
Announcements Last Post
Announcement myUnisa availability 21 to 24 March 2019 03/17/2019 02:24PM
Announcement SoC Curricula 09/30/2017 01:08PM
Announcement Demarcation or scoping of examinations and assessment 02/13/2017 07:59AM
Announcement School of Computing Short Learning Programmes 11/24/2014 08:37AM
Announcement Unisa contact information 07/28/2011 01:28PM
Random Question
May 11, 2011 08:50AM
1.Can a FA and a PDA accept PALINDROM? In my opinion not neither of them can since they can't keep track of all the letters of the first half. But I might be mistaken.

2.Can a FA and a PDA accept the following? a^n b a^n, a^n b^n b a^n

_______________________________________
Don't be different...be the one making a difference
avatar Re: Random Question
May 11, 2011 10:28AM
Very provisionally, I think you may have hit on a general principle there. If the structure of a word depends on the sizes of its components, you have to be able to count that. And to count, you need something like a stack - some extra component in any event.

How does that sound? (Will get back later on details. Right now this quiet little screen is competing with a vacuum machine, a conversation, and a washing machine, for my attention, and my concentration ain't so good).
Re: Random Question
May 11, 2011 10:40AM
That was what I was thinking...but not quite sure.

_______________________________________
Don't be different...be the one making a difference
avatar Re: Random Question
May 11, 2011 11:32AM
Well FA = RegEx, right?

And the only superscript you get for RegEx is star. Oh and +, but that's almost the same thing.

IOW you can't devise a regular expression for a palindrome. That's an alternative to the machine approach.
Sorry, only registered users may post in this forum.

Click here to login