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$
1
  • $\begingroup$ If $\epsilon \in L$ then $L\Sigma^*=\Sigma^*$. $\endgroup$ Commented Oct 18, 2018 at 15:39

1 Answer 1

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 and acknowledge you have read our privacy policy.

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