3. (10 points) Prove that regular languages are closed under the reverse operati

Question

3. (10 points) Prove that regular languages are closed under the reverse operation. Use the following definitions . The reverse of w, written wR, is the string obtained by writing w in the opposite order i.e wnWn-1...W1 . reverse(L) = {w" I w E L} For this problem we require you to: 1. Provide the construction part of the proof from a NFA N to an NFA N using formal definitions. 2. Perform the construction on the following NFA N and provide the state diagram of the result. 91 start 40 42 (You may construct a MSSNFA M instead if you want.) (The proof of correctness is not required.) Created by Paint X

Explanation / Answer

1. Regular Languages are closed under complementation.

So if L is regular then L'= * L is also regular.

Proof------>

If L is regular, then there is a DFA M = (Q,,,q0,F) such that L = L(M).

Then, M' = (Q,,,q0,QF) (switch accept and non-accept states) accepts L.

2. Regular Languages are closed under intersection.

So if L1 and L2 are regular then L1 L2 is also regular.

Proof--------->

Observe that L1 L2 = (L1' L2')'

Since regular languages are closed under union and complementation,

So we have------>

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.