Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Stochastic languages, that is, those accepted by probabilistic automata, are known to not be closed under intersection, union, concatenation, and morphism, even on unary languages.

I have two questions about the Boolean closure of the class of stochastic languages:

  1. Is this class closed under morphisms or concatenation?
  2. Can we show that $\{a^{2^n} \mid n \in \mathbb{N}\}$ is not in it?

Many thanks!

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.