# $L=\{a^ib^i|i\geq0\}$, cfg for $L^2$

$$L=\{a^ib^i|i\geq0\}$$, cfg for $$L^2$$

can you write cfg for $$L^2$$ where $$L=\{a^ib^i|i\geq0\}$$?

the professor's answer sheet says it's $$S\to AA\\ A\to aAb|\lambda$$

but I think it is wrong because two $$L$$ have to be identical with each other.

can you help me figure out if there is cfg describing $$L^2$$?

• It is your assumption that the “two L” have to be the same which is wrong. Take another look at the definition of $L^2$. – Yuval Filmus Oct 17 at 9:05
• @YuvalFilmus after my further study with additional lecture material, I noticed that the concatenation of two language L1 ◦L2 means {xy | x ∈ L1, y ∈ L2}. thank you for your help. – Myeongwon Choi Oct 17 at 9:14

The square language $$L^2$$ is defined as follows: $$L^2 = LL = \{ xy : x,y \in L \}.$$ There is no requirement that $$x = y$$. Indeed, in your case $$L^2 \supsetneq \{ w^2 : w \in L \}$$.