How Can I Describe an NFA that Recognizes w*wR?

[JimmyK]

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.

 

[Valkarie]

Thanks.The solution to this problem is as follows: Let M3=(Q, Σ, T, s3, F3) where Q={q0, q1, q2, q3} Σ=Σ1∪Σ2 (where Σ1 and Σ2 are the alphabets of M1 and M2 respectively) T={(q0,x,q1) | x ∈ Σ1, (q1,x,q2) | x ∈ Σ2, (q2,x,q3) | x ∈ Σ1, (q3,x,q2) | x ∈ Σ2} s3=q0 F3={q2}Basically, M3 is an NFA which consists of four states: q0, q1, q2, and q3. The transition function T has two sub-transitions, one for M1 and one for M2. The transition from q0 to q1 accepts all characters from the alphabet of M1. The transition from q1 to q2 accepts all characters from the alphabet of M2. Then, the transition from q2 to q3 accepts all characters from the alphabet of M1. Finally, the transition from q3 to q2 accepts all characters from the alphabet of M2. The start state of M3 is q0 and the accept state is q2. Therefore, M3 will accept any string which has the form w*wR, where w is a string accepted by M1 and wR is the reverse of w, accepted by M2.