Suppose that there are two probabilistic automata $A_1$ and $A_2$ with a same finite alphabet $\Sigma$. The languages of them are $\mathcal{L}_{1} \subseteq \Sigma^*$ and $\mathcal{L}_{2} \subseteq \Sigma^*$ respectively.

For every input $x \in \Sigma^*$, $\Pr \{ x \in \mathcal{L}_{1}\}=p_1(x)$ and $\Pr \{ x \in \mathcal{L}_{2}\}=p_2(x)$. Whether there exists a probabilistic automaton $A$ satisfying $$\Pr \{ x \in \mathcal{L}\}=\frac{p_1(x)}{p_1(x)+p_2(x)}$$ where $\mathcal{L} \subseteq \Sigma^*$ is the language of $A$?

  • 1
    $\begingroup$ What do you think? Have you tried constructing such an automaton $A$? Have you tried finding $A_1,A_2$ such that no such $A$ exists? $\endgroup$ – Yuval Filmus Feb 5 at 9:32
  • $\begingroup$ What about the trivial answer $\mathcal{L}_1 = \{\}$? $\endgroup$ – orlp Feb 5 at 9:38

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.