• retagged by
1,861 views
1 1 vote

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.

3 Answers

0 0 votes

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

But A2  is regular , here A2  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

0 0 votes

$2A = \{ xy \mid x,y \in A \text{ and } x = y \} \rightarrow$ Not Regular (we can prove using Pumping lemma or Myhill-Nerode Theorem)

To prove that $2A$ is not regular, we use the Pumping Lemma proof by Contradiction here.

Assume $2A$ is regular. 

Then according to the Pumping Lemma, there exists a pumping length $p \ge 1$ such that any $w \in 2A$ with $|w| \ge p$ can be written as $w = xyz$ satisfying:

1) $|xy| \le p$  

2) $|y| > 0$  

3) $xy^i z \in L$ for all $i \ge 0$

Let us assume $\Sigma = \{0,1\}$ and the string $w = \underbrace{1^p0}_{x} \underbrace{1^p0}_{y}$.

Its total length is $2p + 2 \ge p$.

Since $|xy| \le p$, the substring $y$ must lie entirely within the first block $1^p$.  
Let $y = 1^k$ where $1 \le k \le p$.

Now, $ xy^i z = 1^{p + (i-1)k} 0 1^p 0 $

Taking $i = 2$, we get: \( xy^2 z = 1^{p+k} 0 1^p 0\)

Since the number of $1$'s in the first half is not equal to the number of $1$'s in the second half,  
$xy^2 z \notin L$ for $1 \le k \le p$.

This contradicts the Pumping Lemma.

Therefore, $2A$ is not regular.

 

$A^2 = \{ xy \mid x,y \in A \}\rightarrow$ Regular (we can prove using FA) 

As $A$ is regular we can have a finite automata for $A$, say that automata is $D$.
We first make 2 copies of this FA and name it $D_1$ and $D_2$.

From the final state(s) of $D_1$ we add $\epsilon$-transitions to the initial state of $D_2$.

We then make the final states of $D_1$ non-final.
The resulting NFA consisting of all the states and transitions of $D_1$ and $D_2$ alongwith the moidifications will accept the language $AA$ or $A^2$.
(This above statement can be verified formally.)

As a finite automata exists which accepts  $A^2$, we can say it is a regular language.

Position:
Show:

Related questions

21 21 votes
4 answers 4 answers
4.2k
4.2k views
go_editor asked May 27, 2016
4,204 views
For the inter-hostel six-a-side football tournament, a team of $6$ players is to be chosen from $11$ players consisting of $5$ forwards, $4$ defenders and $2$ goalkeepers...
3 3 votes
2 2 answers
973
973 views
go_editor asked May 27, 2016
973 views
Consider the code below, defining the function $A$:A(m, n, p) { if (p == 0) return m+n; else if (n == 0 && p == 1) return 0; else if (n == 0 && p == 2) return 1; else if ...
3 3 votes
2 2 answers
960
960 views
go_editor asked May 27, 2016
960 views
Consider the code below, defining the function $A$:A(m, n, p) { if (p == 0) return m+n; else if (n == 0 && p == 1) return 0; else if (n == 0 && p == 2) return 1; else if ...
3 3 votes
2 2 answers
1.0k
1.0k views
go_editor asked May 27, 2016
1,016 views
Consider the code below, defining the function $A$:A(m, n, p) { if (p == 0) return m+n; else if (n == 0 && p == 1) return 0; else if (n == 0 && p == 2) return 1; else if ...