ugc net dec12

Question

Assume, L is regular language. Let
statements S1 and S2 be defined as :
S1 : SQRT(L) = { x| for some y
with |y| = |x|2, xy ∈L}.
S2 : LOG(L) = { x| for some y with
|y| = 2|x|, xy ∈ L}.
Which of the following is true ?
(A) S1 is correct and S2 is not
correct.
(B) Both S1 and S2 are correct.
(C) Both S1 and S2 are not correct.
(D) S1 is not correct and S2 is
correct.

Answer 1

Both are correct. MAX, MIN, ROOT, HALF, CYCLE, LOG Regular languages are closed under these operations.

Comments

I think log definition is incorrect |y| = 2|x|

---

@srestha

in $S_1$ : $|y|= |x|^2$ and in $S_2$ : $|y|= 2^{|x|}$

---

Could you prove that regular expressions are closed over all those operations?