Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.