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) A2 := { 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


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

Sumit Verma sumitverma 1 Dec 2016 03:43 pm

A2 is always regular when A is regular. Suppose M = (Q, Σ, I, ∆, F) is an NFA recognizing A. The language A2 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.

rameshbabu somethingnew 17 Jan 2017 06:10 pm

regular  language is closed under concatination, so Q is correct

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