Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

NFA for recognizing w*wR

  1. Sep 20, 2011 #1
    I have an example where we have an NFA that accepts w and is of the form M1=(Q, Σ, T, s1, F1) and another that accepts wR (the reversal of w) of the form M2=(Q, Σ, T, s2, F2). This is all high level, and theory based, so we don't know what w or the containing language actually is. Now, I need to describe an NFA that accepts w*wR in the same form, M3=(Q, Σ, T, s3, F3), by formally describing each element in the tuple.

    I found this old PDF: http://cs.nyu.edu/courses/fall03/V22.0453-001/hw5.pdf where problem 3 looks very similar to my question and provides a solution I don't quite get.

    I'm just having trouble describing what M3 would be like. I realize that in order for a string to be accepted, the set pair when finished would need to be the same state, i.e. (q0, q0), but am lost otherwise. Any insight would be appreciated.
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?