19 views

Let $L$ be a regular language. Consider the constructions on $L$ below:

1. repeat $(L) = \{ww \mid w \in L\}$
2. prefix $(L) = \{u \mid ∃v : uv \in L\}$
3. suffix $(L) = \{v \mid ∃u : uv \in L\}$
4. half $(L) = \{u \mid ∃v : | v | = | u | \text{ and } uv \in L\}$

Which of the constructions could lead to a non-regular language?

1. Both I and IV
2. Only I
3. Only IV
4. Both II and III