Rigorous proof against pseudorandom generator I am trying to teach myself the principles of cryptograhpy, and want to solve the following question:

Let G be the algorithm that takes an input x = (x1, . . . , xn) from
{0, 1} n (so each xi ∈ {0, 1}) and outputs the string G(x1, . . . ,
xn) = (x1, . . . , xn, x1 ⊕ x2) in {0, 1} n+1. Rigorously prove that G
is not a pseudorandom generator.

So, we would want to prove that either expansion doesn't hold (for all n, l(n) &gt; n), which, in this case, would mean that for each x, the corresponding G &gt; x, or pseudorandomness doesn't hold ( For efficient algorithm D, there is a negligible function 'n' such that:

Pr[D(r) = 1]-Pr[D(G(s)) = 1] $\leq$ $\epsilon$(n),
where 'r' is uniform on {0,1}$^{l(n)}$ and 's' is uniform on {0,1}$^n$

), which, in this case, means that we need to prove that there does not exist a function n such that the difference of the probabilities of the function D(r) and D(G(s)) is very small.
Now, I understand these concepts, but I am  having trouble approaching this problem practically... what would be the best way to start?
Your definition of pseudorandomness is misleading. A better definition would start with a function with "expansion", and then state then it is indistinguishable from random. In your case, the function is "expanding" since it takes $n$ bits and outputs $n+1$ bits. However, the $n+1$ bits it produces don't look random. Can you tell why?