CMI2014-B-01

Question

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

$2A:=\{xy \mid x, \: y \in A \text{ and } x=y\}$

$A^2 :=\{xy \mid x, \: y \in A\}$

One of these operations necessarily leads to a regular language and the other may not. Identify which is which. For the regular operation, give a proof that it is regular. For the non-regular operation, give an example of an $A$ such that applying the operation on it results in a non-regular language.

Answer 1

2A is CSL . Because 2A={xx | x,y∈A and x=y}

But A²  is regular , here A²  could takes any value whose multiplication is a square (1,4),(3,27) . So, A is regular means any power of A is also regular

Comments

2A is CSL and not CFL. But you have to prove it as per question :)

$A^2$ is regular. But I do not get what multiplication has to do here. To prove that $A^2$ is regular you can construct a FA for $A^2$ assuming one for $A$.

---

But sir how can I draw FA for A² because here x and y depends on each other

and say x=2 then y=8,128 etc. rt?

and here A={2,8,128.....} and A² ={16,256.........}

---

product automata ?

---

otherwise how do u think

---

Suppose A={00,01,10,11}//construct FA for length 2 string

 then      A² =A.A={00,01,10,11}{00,01,10,11}

                         ={0000,0001,0010,0011,0100.................1111}//FA for length 4 string

---

^^ concatenation

---

@praveen Sir is this work here ? Or we use  another approach ?

Answer 2