2
$\begingroup$

Given a formal language L, is $L \subset L^*$ or is $L \subseteq L^*$?

To give context, I am tasked with proving whether or not there exists a language such that $(L^*)^c = (L^c)^*$. Assuming the logic behind my proof is correct, I've concluded that if $L \neq L^*$ then $(L^*)^c$ cannot equal $(L^c)^*$. I won't go into my proof as it's the not primary subject of my question (that is, unless someone is interested enough to check my work).

Thanks for any assistance!

  • 0
    Yes, it stands for the complement. I will edit the post to use a more familiar notation.2011-12-04

1 Answers 1

2

Both are possible. For example, we have $\{a\}\subsetneq \{a\}^*$, but $\{a^n\mid n\ge 0\}=\{a^n\mid n\ge 0\}^*$.

For your "contextual" question, consider $L=\varnothing$...

  • 0
    Why shouldn't it?2011-12-04