Theory of Computation- Regular Expression

Question

Let $L$ be a language recognizable by a finite automaton. The language $Reverse(L)$=$\{\text{x such that x is the reverse of y where y belongs to L}\}$ is a -

• A. Regular Language
• B. Context-sensitive language
• C. Context-free language
• D. Phrase-structured language

According to me, the answer should be all of $a,b,c$ and $d$. But it is given $a$ in the study material of my coaching institute. What is the correct answer?

Comments

@Mamta Satywali,  Thanks! But she did not talk about phrase structured languages.. I have not seen anywhere where it is written that unrestricted and phrase structured  both are same.. Can you please provide link regarding it?

---

Refer to same video @31:20

---

Thank u so much..

Answer 1

Regular languages are closed under Reversal [Reverse(L) can be obtained by reversing directions in FSA of L & changing initial state to final and final to initial(for more than one final states, draw an epsilon move from each one of them to a single final state] So the answer is A.

But you are right in the sense that all regular languages are CFL/CSL/Phrase structured. Still best choice would be A.

Comments

Correction :- In Reverse , We change initial state to final state and final state(s) to initial state(s)...If we get more than one initial state after reversal then we make a new initial state and connect those initial states by null/e-moves...

---

Sure. I was confused with complement there.Thanks.

Answer 2

Regular Language are close under Reversal operation. So most suited  option is A, because Regular  Language is smallest set in Chomsky Grammar (Language) classification. Every Recursive enumerable or CSL or Context free grammar  are not always Regular.