GATE CS 1987 Q2h — Regular and Context-free Languages

The given statement is TRUE (represented by 1).

Proof of Closure under Reversal

If a language $L$ is regular, then its reversal $L^R = \{w^R \mid w \in L\}$ is also regular. This can be proven using two standard approaches:

1. Using Finite Automata

Let $M = (Q, \Sigma, \delta, q_0, F)$ be a Deterministic Finite Automaton (DFA) that accepts $L$. We can construct a Non-deterministic Finite Automaton (NFA) $M^R$ that accepts $L^R$ as follows:

• Reverse the direction of all transition arrows in $M$.
• Make the start state $q_0$ of $M$ the only final state of $M^R$.
• Create a new start state $s_0$ for $M^R$ and add $\epsilon$-transitions from $s_0$ to all the original final states in $F$.

Since we can construct an NFA $M^R$ that accepts $L^R$, the language $L^R$ is regular.

2. Using Regular Expressions

If $r$ is a regular expression representing $L$, we can construct a regular expression $r^R$ for $L^R$ inductively:

• $\emptyset^R = \emptyset$, $\epsilon^R = \epsilon$, and $a^R = a$ for any $a \in \Sigma$.
• $(r_1 + r_2)^R = r_1^R + r_2^R$
• $(r_1 \cdot r_2)^R = r_2^R \cdot r_1^R$
• $(r^*)^R = (r^R)^*$

Since $r^R$ is a valid regular expression, $L^R$ is regular.

Thus, regularity is preserved under string reversal.