9
$\begingroup$

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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.