# NFA for reading in a string and then reading it in reverse for acceptance

• Sep 18th 2011, 04:43 PM
LostProjectile
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?
• Sep 19th 2011, 03:29 AM
emakarov
Re: NFA for reading in a string and then reading it in reverse for acceptance
No, the language $\displaystyle L=\{ww^R\mid w\in\Sigma^*\}$ is not regular if $\displaystyle |\Sigma|>1$. This can be proved using the pumping lemma or the Myhill-Nerode theorem.

Consider $\displaystyle \Sigma=\{a,b\}$. 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 $\displaystyle L\cap L'=\{a^nbba^n\mid n\ge0\}$. It's easy to show that the latter language is not regular by the pumping lemma.
• Sep 19th 2011, 12:27 PM
LostProjectile
Re: NFA for reading in a string and then reading it in reverse for acceptance
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?
• Sep 19th 2011, 12:40 PM
emakarov
Re: NFA for reading in a string and then reading it in reverse for acceptance
What is w? The automaton must not depend on individual words; it must accept $\displaystyle ww^R$ 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.
• Sep 19th 2011, 01:23 PM
LostProjectile
Re: NFA for reading in a string and then reading it in reverse for acceptance
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.
• Sep 19th 2011, 01:37 PM
emakarov
Re: NFA for reading in a string and then reading it in reverse for acceptance
This is a little vague. First, for every concrete $\displaystyle w$ you can write automata that accept $\displaystyle w$, $\displaystyle w^R$ and $\displaystyle ww^R$. Beyond that, I need to see a more formal description of automata that supposedly could accept $\displaystyle \{ww^R\mid w\in\Sigma^*\}$.
• Sep 20th 2011, 06:17 AM
LostProjectile
Re: NFA for reading in a string and then reading it in reverse for acceptance
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.
• Sep 20th 2011, 10:31 AM
LostProjectile
Re: NFA for reading in a string and then reading it in reverse for acceptance
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.
• Sep 20th 2011, 12:42 PM
emakarov
Re: NFA for reading in a string and then reading it in reverse for acceptance
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 $\displaystyle w\in L\cap L^R$ where $\displaystyle L^R=\{w^R\mid w\in L\}$ does not imply that $\displaystyle w$ is a palindrome. For example, if L = {ab, ba}, then $\displaystyle L^R=L$ and $\displaystyle L\cap L^R=L$, but neither of the words in L is a palindrome.