##### Let A be a regular language. Consider the foll...

Let A be a regular language. Consider the following operations on A:

(P) 2A := { xy | x, y ∈ A and x = y}

(Q) A^{2} := { xy | x, y ∈ A}

Which of these operations necessarily leads to a regular language,

(A) Both P and Q | |

(B) Only P | |

(C) Only Q | |

(D) Neither P nor Q |

Hint:

<div class="tex2jax"></div>

A

^{2 }is always regular when A is regular. Suppose M = (Q, Σ, I, ∆, F) is an NFA recognizing A. The language A^{2 }is recognized by the NFA N = (Q×{0, 1}, Σ, I × {0}, ∆' , F × {1}) where• ∆' ((q, i), a,(q' , j)) iff

– either ∆(q, a, q' ) and i = j, or

– q ∈ F, q' ∈ I, i = 0, j = 1, a = ε.

The automaton N stays in the 0-states while verifying that a portion of the input string x is in A, and nondeterministically guesses the position at which has to verify that remainder of the input is in A.

2A need not be regular even if A is regular. Consider A = Σ* , a regular language. 2A is the language {xx | x ∈ Σ*}, which is not even context-free, and hence not regular.

regular language is closed under concatination, so Q is correct

ans ww is not reg, not cfl its csl so P is not reg