Question

Computer Science Theory Question
Please Answer correctly and clearly with explanation if possible.

=> For a string w = w₁w₂...w_n where w_i ∈ Σ, we define the reverse of w as w^R= w^_n...w₂w₁ (namely the string w in reverse order). For a languageLwe defineLR={wR|w∈L}.

===> Prove that for every regular expression α there is a regular expression β of the exact same length | β |=|α |, such that L(β) = (L(α))^R.

(NOTE - Here In this problem you are asked to work with regular expressions and have an extra requirement that the length is preserved. So, it is not sufficient to prove that regular languages are closed under reversal.)

Answer 1

If a NFA accepts α and then we create N' that accepts β such that it accepts where intial and final states are reversed. such that inital states in N becomes final states in N' and final states in N becomes inital states in N'.

Length is kept equal of both the strings.

Reading string right to left instead of left to right. we just reverse the NFA and if the language fits into the NFA (N') then we can say that the β is also regular if α is regular.

We can say that regular languages are still regular when reversed.

If you still got some doubts. Leave a comment