Cheap and Secure Web Hosting Provider : See Now

Kleene algebra - powerset class vs class of all regular subsets

, , No Comments
Problem Detail: 

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.

Asked By : Marek Milkovič
Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/48378

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback