From my understanding in the first part of the question we bound the algorithm $ f(x,y) $ to a specific pseudorandom number generator $ r() $. In this case the answer depends on the PRNG used.

Consider that $ r() $ is a Linear Congruential Generator (LCG) with known parameters. Then $ f(x,y) $ could simply test if

$ y \equiv (a \cdot x + c) \mod{M} $

and output "pseudorandom" if the equality holds.

This algorithm would always be correct if the input comes from $ r() $ and will fail to produce a correct result in case the input comes from $ q() $, if the two random numbers form a correct sequence for the LCG. If we consider 32 bit numbers then, because we have exactly one correct $y$ for each $x$, there are $ 2 ^{32} $ inputs for which the algorithm will output an incorrect result out of $ 2 ^{64} $ total possible inputs. So the error probability of the algorithm is $ 1 / 2^{32} $.

A similar algorithm could be used in the case of Mersenne twister. However because of the larger state of the generator, two consecutive outputs will not give any information, so a larger vector is needed ($n=624$ is enough). Note that this technique will fail if the output of the generator hides its internal state (ex. with a cryptographically strong hash function).

From my understanding in the first part of the question we bound the algorithm $ f(x,y) $ to a specific pseudorandom number generator $ r() $. In this case the answer depends on the PRNG used.

Consider that $ r() $ is a Linear Congruential Generator (LCG) with known parameters. Then $ f(x,y) $ could simply test if

$ y \equiv (a \cdot x + c) \mod{M} $

and output "pseudorandom" if the equality holds.

This algorithm would always be correct if the input comes from $ r() $ and will fail to produce a correct result in case the input comes from $ q() $, if the two random numbers form a correct sequence for the LCG. If we consider 32 bit numbers then, because we have exactly one correct $y$ for each $x$, there are $ 2 ^{32} $ inputs for which the algorithm will output an incorrect result out of $ 2 ^{64} $ total possible inputs. So the error probability of the algorithm is $ 1 / 2^{32} $.

A similar algorithm could be used in the case of Mersenne twister. However because of the larger state of the generator, two consecutive outputs will not give any information, so a larger vector is needed ($n=625$ is enough). Note that this technique will fail if the output of the generator hides its internal state (ex. with a cryptographically strong hash function).