I am currently studying materials for my uni subject. There are two examples of Kleene algebras, but I don't see what is the difference between them.

  • Class ${2^{\Sigma}}^{*}$ of all subsets of $\Sigma^{*}$ with constants $\emptyset$ and $\{\varepsilon\}$ and operations $\cup$, $\cdot$ and $*$.
  • Class of all regular subsets of $\Sigma^{*}$ with constants $\emptyset$ and $\{\varepsilon\}$ and operations $\cup$, $\cdot$ and $*$.

What is the difference between ${2^{\Sigma}}^{*}$ and all regular subsets of $\Sigma^{*}$? What is that difference I don't see? Thanks in advance.


The difference between the two is that $2^{\Sigma^*}$ contains all languages over $\Sigma$, whereas the class of all regular subsets of $\Sigma^*$ contains only the regular languages over $\Sigma^*$. So if $L$ is a non-regular language over $\Sigma$ then $L \in 2^{\Sigma^*}$ while $L$ doesn't belong to the set of all regular languages over $\Sigma$. For any $\sigma \in \Sigma$, you can take $L = \{ \sigma^{n^2} : n \geq 0 \}$, for example.

| cite | improve this answer | |
  • $\begingroup$ Thank you. I didn't think of this that way. Somehow, I automatically assumed only regular languages. My bad. $\endgroup$ – Marek Milkovič Oct 18 '15 at 7:10

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.