The minimal probabilistic and quantum finite automata recognizing uncountably many languages with fixed cutpoints
share
It is known that 2-state binary and 3-state unary probabilistic finite automata and 2-state unary quantum finite automata recognize uncountably many languages with cutpoints. These results have been obtained by associating each recognized language with a cutpoint and then by using the fact that there are uncountably many cutpoints. In this note, we prove the same results for fixed cutpoints. Thus, each recognized language is associate with an automaton (i.e., algorithm), and the proofs use the fact that there are uncountably many automata. For each case, we present a new construction.
READ FULL TEXT