New answers tagged

0

As Emil explained in a comment: The sides are interchangable when defining the Rabin condition - my professor defined the left side as the one that is required to be visited infinitely often while Wikipedia and the paper I've mentioned define the right side as the one that is required to be visited infinitely often. Whichever the side that has to be visited ...


2

I seems that I was quite confused back then. This language class is precisely the language class of those languages, whose commutative closure is regular. Let $\Sigma = \{a_1, \ldots, a_k\}$. One implication is given in the question. For the other, suppose the commutative closure of $L \subseteq \Sigma^*$ is regular, i.e., the set $p^{-1}(p(L))$ is regular. ...


0

Think set theory. We have for L1 $$ (A - {a}) \subset A^* $$ $$ A^*.(A-{a}).A^* \subset A^* $$ Then $$ S1 = A^*.\{b\} $$ $$ S1 = A^*.(A)^*.A^*.\{b\} $$ $$ S2 = (A^*.(A-{a})).A^*.\{b\} $$ $$ S1 - S2 = a^*b$$ Basically you removed everything from A* that does not have a, then you end up with a*. Same argument goes for L2. Then: $$ L1.L2 = a*.b.b* = a^*.{b+b*}...


Top 50 recent answers are included