Question

Show that if A is a regular set, then\({{\bf{A}}^{\bf{R}}}\), the set of all reversals of strings in A, is also regular.

Short answer

Therefore, the given statement is true. That is, if A is a regular set, then\({{\bf{A}}^{\bf{R}}}\), the set of all reversals of strings in A, is also regular.

Step-by-step solution

General form

Regular expressions (Definition): The regular expressions over a set I are defined recursively by:

The symbol \(\emptyset \) is a regular expression.

The symbol \({\bf{\lambda }}\)is a regular expression.

The symbol xis a regular expression whenever\({\bf{x}} \in {\bf{I}}\).

The symbols \(\left( {{\bf{AB}}} \right){\bf{,}}\left( {{\bf{A}} \cup {\bf{B}}} \right){\bf{,}}\) and \({\bf{A*}}\) are regular expressions whenever A and B are regular expressions.

The sets represented by regular expressions are called regular sets.

A rule of regular expression represents a set:

\(\emptyset \) represents the empty set, that is, the set with no strings;

\({\bf{\lambda }}\) represents the set\(\left\{ {\bf{\lambda }} \right\}\), which is the set containing the empty string;

xrepresents the set \(\left\{ {\bf{x}} \right\}\) containing the string with one symbol x;

(AB) represents the concatenation of the sets represented by Aand by B;

\(\left( {{\bf{A}} \cup {\bf{B}}} \right)\)represents the union of the sets represented by Aand by B;

\({\bf{A*}}\) represents the Kleene closure of the sets represented by A.

Structural Induction:A proof by structural induction consists of two parts. These parts are

Basis step: Show that the result holds for all elements specified in the basis step of the recursive definition to be in the set.

Recursive step: Show that if the statement is true for each of the elements used to construct new elements in the recursive step of the definition, the result holds for these new elements.

Step 2: Proof of the given statement

Given that, the set of all reversals of strings in A, is also regular.

To prove: If A is a regular set, then\({{\bf{A}}^{\bf{R}}}\).

Proof: Using Structural induction.

If the regular expression for A is \(\emptyset {\bf{, \lambda ,}}\)or x, the result is trivial.

Otherwise, suppose the regular expression for A is\({\bf{BC}}\).

Then \({\bf{A = BC}}\)where B is the set generated by B and C is the set generated by C.

By the inductive hypothesis there are regular expressions \({\bf{B'}}\) and \({\bf{C'}}\) that generate \({{\bf{B}}^{\bf{R}}}\) and\({{\bf{C}}^{\bf{R}}}\), respectively.

Because,

\(\begin{array}{c}{{\bf{A}}^{\bf{R}}}{\bf{ = }}{\left( {{\bf{BC}}} \right)^{\bf{R}}}\\{\bf{ = }}{{\bf{C}}^{\bf{R}}}{{\bf{B}}^{\bf{R}}}\end{array}\)

\({\bf{C'B'}}\)is a regular expression for\({{\bf{A}}^{\bf{R}}}\).

If the regular expression for A is\({\bf{B}} \cup {\bf{C}}\), then the regular expression for \({{\bf{A}}^{\bf{R}}}\) is \({\bf{B'}} \cup {\bf{C'}}\)because\({\left( {{\bf{B}} \cup {\bf{C}}} \right)^{\bf{R}}} = \left( {{{\bf{B}}^{\bf{R}}}} \right) \cup \left( {{{\bf{C}}^{\bf{R}}}} \right)\).

Finally, if the regular expression for A is\({\bf{B*}}\), then it is easy to see that \(\left( {{\bf{B'}}} \right){\bf{*}}\) is a regular expression for\({{\bf{A}}^{\bf{R}}}\).

Conclusion: So, A is a regular set, and then \({{\bf{A}}^{\bf{R}}}\) is also regular set.

Hence proved.