Thread: NFA for reading in a string and then reading it in reverse for acceptance

Is it possible to create an NFA that processes a string w, then must do the reversal of w to get to a final state? This seems like it might be problematic as when you do the reversal, you must essentially follow the exact same path as w in reverse. Is it possible for such a machine to ensure that?

No, the language is not regular if . This can be proved using the pumping lemma or the Myhill-Nerode theorem.

Consider . Regular languages are closed under intersection, and the language L' described by the regular expression a*bba* is regular, so if L is regular, then so it . It's easy to show that the latter language is not regular by the pumping lemma.

I've been thinking about this further, and I'm wondering what your opinion is if we ran both the machine that accepts w and the reverse of w at the same time. Could we then somehow conclude that the string is accepted if the two end states are final and the same state?

What is w? The automaton must not depend on individual words; it must accept for any w.

I am not sure this is answering the question, but he fact that two words drive a finite automaton to the same final state is not sufficient to claim that the words are equal. The automaton way have a loop which can be run any number of times: this is the idea of the pumping lemma.

My teacher said during the example, that once you've created an NFA for w and an NFA for the reversal of w then the NFA for the acceptance of w concatenated with its reversal, where w is a string in any language L, can be thought of by running the NFA that runs w forward and running the NFA that runs w's reversal and if see if you end up with a state pair that is the same. As you said, this doesn't make sense to me because of looping so I've been dwelling on this example.

This is a little vague. First, for every concrete you can write automata that accept , and . Beyond that, I need to see a more formal description of automata that supposedly could accept .

He's just giving us these details in these very vague ways. He's saying that given these details, you should be able to formalize a description of this NFA. I don't think he's saying that you can actually create it as as you said, we don't know concretely what w is. He's just saying we can describe this NFA in formalized terms using the formalized descriptions of the other two NFAs, that is the one that runs w and the one that runs w's reversal, using cartesian products.

Sorry if my manner is description of vague or confusing, this is most likely to me being confused myself. I just know he's saying describe this machine in terms of the 5-tuple of the other two, like M = (Q, Σ, δ, q0, F), and I'm concerned this is going to appear on a test.

I believe problem 3# here is what I'm going for: http://cs.nyu.edu/courses/fall03/V22.0453-001/hw5.pdf

Then I need to find a formal definition of the machine M3 that is described.

This problem concerns using Turing machines to decide whether an automaton has some property.

By the way, I think the solution in the PDF file is incorrect because where does not imply that is a palindrome. For example, if L = {ab, ba}, then and , but neither of the words in L is a palindrome.