Random Question

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

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).

That was what I was thinking...but not quite sure.

_______________________________________
Don't be different...be the one making a difference

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.