1
$\begingroup$

I've been looking at questions about the regular concatenation of two languages; one question said that the concatenation of $\{0^n1^n|n\geq 0\}$ and $\Sigma^*$ was regular (over the alphabet $\Sigma = \{0,1\}$). Another provided a counterexample by the concatenation of $\{a^{n^2}b|n\geq 0\}$ with $\Sigma^*$, which is irregular (over the alphabet $\Sigma = \{a,b\}$). Could someone provide clarification as to why some concatenations with $\Sigma^*$ are regular while others aren't? Both cases concatenate an irregular language unrecognisable by a DFA to one that is, and I don't understand how this produces a language that is recognisable.

Links to source questions: https://math.stackexchange.com/questions/649335/are-languages-regular-if-their-concatenation-is-regular Why is $\Sigma^*$ concatenated with some language regular?

$\endgroup$
  • $\begingroup$ If $\epsilon \in L$ then $L\Sigma^*=\Sigma^*$. $\endgroup$ – Yuval Filmus Oct 18 '18 at 15:39
1
$\begingroup$

In the first case, $n$ can be 0, and the concatenation will produce $\Sigma^*$. So any other value of $n$ is irrelevant; no other strings could be added. If the restriction were $n>1$, then the concatenation would not be regular.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.