The reversal of a string
2) Proof: The reversal of a string a1a2…an is the string written backwards anan-1…a1. We use WR for the reversal of string w. The reversal of a language L, written LR (Reverse of the language), is the language consisting of the reversals of all its strings.
Examples: L = {001, 10, 111} LR = {100, 01, 111}
Closure property under reversal – if L is a regular language, then so is LR.
Proof1 – Let L be recognized by an FSA A.
Turn A into an FSA for LR, by:
1. Reversing all arcs
2. Make the old start state the new sole accepting state.
3. Create a new start state P0, with σ (P0, q) = F (The old accepting states)
Proof2 – Assume L is defined by a regular expression E. We show that there is another regular expression ER such that L(ER) = (L(E)). R that is, the language ER is the reversal of the language of E.
Basis: If E is q, Ø of a, then ER = E
Induction: There are three cases, depending on the form of E.
1. R = FR + GR
Justification: The reversal of the union of two languages is obtained by computing the reversal of the two languages and taking the union of these languages.
2. E = FG. Then ER = GR.FR
Note: We reverse the order of the two languages, as well as reversing the languages themselves. Justification: In general, if a word w € L(E) is the concatenation of w1 € L(F) and w2 € L(G) then WR = WR2.WR1
3. E = F*. Then ER = (FR)*
Justification: Any string w € L(E) can be written as w1w2…wn, where each wi is in L(F). But wR = wRn…wR2..wR1 and each wRi is in L(ER), so wR is in L((FR)*). Conversely, any string in L((FR)*) is of the form w1w2…wn where each wi is the reversal of a string in L(F).
The reversal of this string is in L(F*) which is in L(E). We have shown that a string is in L€ if its reversal is in L((FR)*). Therefore, its proved.