World's most popular travel blog for travel bloggers.

[Answers] Proving that the reversal of a language reversal is that language

, , No Comments
Problem Detail: 

I am trying to prove that with language L, (L^R) ^R =L So that the reversal of the reversal of the language is the original language L.

I have proved that before with a string not language (let's call it a string 's').

(s^R)^R = s. Proof by induction on the length of s.  Base: |s|=0. s=ε. (s^R)^R =(ε^R)^R =(ε)^R =ε=w. Induction hypothesis: if 0 ≤ |x| ≤ n, then (x^R)^R = x. Induction step: Suppose |s| = n + 1. Then we can write s = xa, where a is a symbol and 0≤|x|≤n. Then (s^R)^R = ((xa)^R)^R since s = xa = (ax^R)^R since (xy)^R = y^R*x^R (think of a as a string of length 1) = (x^R)^R*a^R same as previous line but using outer R = (x^R)^R*a using the second part of the definition of reverse with u=ε. = xa by the induction hypothesis  = s since s = xa 

How can this reasoning the expanded to Languages? In essence I am proving the same operation, but I am dealing with languages instead of strings. Languages are made up of strings. Thoughts?

Asked By : user3295674

Answered By : Anton Trunov

Well, we don't really need induction here.

We want to prove that for any language $L$ holds the statement

$$\left( L^R \right)^R = L.$$

(1) Let $s \in \left( L^R \right)^R$. Then there exists a (unique) string $t \in L^R$, such that $s = t^R$. The situation is analogous with $t$: there exists a (unique) string $u \in L$ such that $t = u^R$. From that we get $s = t^R = \left( u^R \right)^R = u$, so $s \in L$.

(2) Let $s \in L$. Observe that $s^R \in L^R$ and $\left( s^R \right)^R \in \left( L^R \right)^R$, again using the fact that $s = \left( s^R \right)^R$ we get that $s \in \left( L^R \right)^R$.

From (1) and (2) follows the statement of the theorem.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/52037

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback