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
    Does $\neg L$ stand for the complement of a language? I have seen $\bar L$, $L'$ and $L^c$ to denote complements, not $\neg L$. [I prefer the notation $L^c$ to the other two.]2011-12-04
  • 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
    Thanks! I had been considering when L is the null set, but I wasn't sure whether the null set was a valid language.2011-12-04
  • 0
    Why shouldn't it?2011-12-04