Algebraic Language

41 Views Asked by At

I would like to have a piece of advice to help me proof the last question of my exercise

  1. I had to prove that $L = \{a^nb^nc^md^{3 \times m}, n, m \geq 1\}$ is an algebraic language (done).

  2. I needed to compute $\frac{1}{2} L = \{x, \exists y \in \Sigma^*, x.y \in L \text{ and } |x| = |y| \}$

enter image description here

For me, this set is the union of $L_1, L_2, L_3$.

  1. Prove that $\frac{1}{2}L$ is not an algebraic language.

To do that I wanted to use the pumping lemma, but I am stuck. It seems clear that if the word $x\gamma y$ contains only letter a or b then the word $\beta x^i \gamma y^i \delta$ cannot be in the set $\frac{1}{2}L$ as the number of a (respectively b) will be different compared to the number of b (respectively a) with i an integer. But in case that the word $x\gamma y$ contains both letter a and b, I'm not sure if x and y can hold a different letter but the same number (ie: x = aaa and y = bbb for). If so, then the word $\beta x^i \gamma y^i \delta$ is in $\frac{1}{2}L$.

Thusly, I would appreciate it if someone would give me a tip or just point out what is wrong with my proof.

Thanks in advance.