Why L' is not regular?

Question

$$L'=\{ww|w\in L\}$$

I need to give an example of regular language L for which the concatenation of 2's $w$ gives $L'$ which is not regular.

How can I give such an example if according to closure properties for concatenation $L1L2$. each of them is regular,concatenation gives me a regular output.

Answer 1

I think that you are having trouble distinguishing the difference between regular and non-regular languages, so I try to give a short explanation before I give you an example.

We call a language $L$ regular if it can be decided if a word is in the language with an algorithm/a machine with constant (finite) memory by examining all symbols in the word one after another. E.g. the language consisting just of the word $ab$ is regular, as we can decide whether a word is in it without requiring arbitrary amounts of memory; you just check whether the first symbol is $a$, whether the second is $b$, and whether any more symbols follow. The construct of a finite-state machine is used to prove whether a language is regular or not.

So if we take $L_1 = \{a^nb \space | \space n \in \mathbb{N}\}$; this is a regular language as you don't need arbitrary amounts of memory, the concatenation $L_1' = \{ a^nba^nb \space | \space n \in \mathbb{N} \}$ would be non-regular as you need a memory to 'remember' how many $a$'s the first one has as the second $a$ is required to have the same amount.

Now as gnasher729 already stated, $L_2 = \{a^*b\}$ is regular and $L'_2 = \{ a^*ba^*b\}$ would also be regular as we do not have to remember how many $a$'s there are. We only need a finite-state machine to check if the last $a$ in each part is followed by one $b$.

Answer 2

Let L = a*b. LL is regular ($a^nba^mb$). But the language you are asked to check is $a^nba^nb$ where the two n’s are the same. There are plenty of proofs in the last days here that you can adapt. And Myhill-Nerode is super easy.