Sign up ×
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|cite|improve this question

Your Answer


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

Browse other questions tagged or ask your own question.