Results 1 to 9 of 9

Math Help - NFA for reading in a string and then reading it in reverse for acceptance

  1. #1
    Newbie
    Joined
    Sep 2011
    Posts
    17

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773

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

    No, the language L=\{ww^R\mid w\in\Sigma^*\} is not regular if |\Sigma|>1. This can be proved using the pumping lemma or the Myhill-Nerode theorem.

    Consider \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 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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2011
    Posts
    17

    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773

    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 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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Sep 2011
    Posts
    17

    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773

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

    This is a little vague. First, for every concrete w you can write automata that accept w, w^R and ww^R. Beyond that, I need to see a more formal description of automata that supposedly could accept \{ww^R\mid w\in\Sigma^*\}.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Sep 2011
    Posts
    17

    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Sep 2011
    Posts
    17

    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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773

    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 w\in L\cap L^R where L^R=\{w^R\mid w\in L\} does not imply that w is a palindrome. For example, if L = {ab, ba}, then L^R=L and L\cap L^R=L, but neither of the words in L is a palindrome.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. help reading maple PLEASE
    Posted in the Math Software Forum
    Replies: 0
    Last Post: December 14th 2010, 10:05 AM
  2. Am I Reading Too Much Into This?
    Posted in the Calculus Forum
    Replies: 4
    Last Post: July 9th 2008, 09:26 PM
  3. Help reading notation
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 8th 2008, 08:22 AM
  4. Reading a function
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: October 1st 2007, 10:35 AM
  5. Book Reading
    Posted in the Statistics Forum
    Replies: 2
    Last Post: January 30th 2007, 12:34 PM

Search Tags


/mathhelpforum @mathhelpforum