Probabilistic automata—a problem of Paz

Paz 1967defines ε-approximation of probabilistic finite acceptors (p.ac.) and proves that the class of ε-approximable p.ac. languages is contained in the class of type 0 languages, but not in the class of regular sets. He conjectures that the class is not contained in the class of context-free languages. We prove that this conjecture is true. Our counter example is a modification of Paz's example of a nonregular language