Reverse of a Regular Language - MathOverflow [closed] most recent 30 from http://mathoverflow.net 2013-06-19T18:00:22Z http://mathoverflow.net/feeds/question/77988 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/77988/reverse-of-a-regular-language Reverse of a Regular Language guim79 2011-10-13T03:00:59Z 2011-10-13T03:00:59Z <p>Hi all,</p> <p>This is a homework. I want to know if I'm on the right way, The problem is: show that if L is a subset of sigma* is a regular language, then the following language is also a regular one:</p> <pre><code>$L^'$ ={w | there is x, y $\in \sigma*$ | w = xy $\wedge$ yx $\in$ to L} </code></pre> <p>To do that, I've constructed a NFA that accept L. Then I've inverted the transitions of the NFA so that it could accept the inverted language. I Made old initial state a final state, and then I added a new initial state.</p> <p>Is that correct? Thanks.</p>