0
$\begingroup$
  1. If $A$ is a non-context free language, is $A^*$ a regular language?
  2. If $A$ is a non-context free language and $B$ is a regular language, is it possible that their concatenation is a regular language?
$\endgroup$
  • 1
    $\begingroup$ What do you think? What have you tried, and where did you get stuck? $\endgroup$ – Yuval Filmus Apr 15 '19 at 18:07
1
$\begingroup$

Let $A$ be $\{a^p\mid p\text{ is prime}\}$. Let $B$ be $\{a\}^*$.

Both $A^*$ and $A\circ B$ are regular. $A^*$ is $\epsilon+aaa^*$ and $A\circ B$ is $aaa^*$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ True, but it's still regular. I'll fix it. $\endgroup$ – rici Apr 11 '19 at 4:32
  • 1
    $\begingroup$ Note that, if $A$ is a unary language (i.e., uses only a single letter alphabet) as in this case, then in fact the star $A^*$ is always regular. See this question: Show that the Kleene star of any unary language is regular. It seems the same holds for $A \cdot \{a\}^*$, because that language consists of all strings longer than the shortest in $A$. $\endgroup$ – Hendrik Jan Apr 11 '19 at 8:52

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