Simple question about pseudorandom generator I am stuck on the following question related to pseudorandom generator and any help would be appreciated.


  Let $G:\{0,1\}^k \to \{0,1\}^{k+1}$ be a pseudorandom generator. Define $G&#39;:\{0,1\}^{2k}  \to \{0,1\}^{2k+2}$ by $G&#39;(x_1x_2)=G(x_1)G(x_2)$ where $x_1, x_2 \in \{0,1\}^k$.
  
  Prove that $G&#39;$ is not a pseudorandom generator in general.


I don't think it is necessary (and feasible) to find a counter-example $G&#39;$ since it requires us to find a pseudorandom generator $G$, (which means we will have proved the existence of pseudorandom if we can find such $G$) so normally how can we tackle this kind of problem?

Thank you very much in advance. :)
I assume you mean a cryptographic PRG.

Let's assume on the contrary that the $G&#39;$ is not secure. So let $A$ be a probabilistic Turing machine that distinguishes the output of $G&#39;$ from uniformly random bits.

Let $x_1,x_2$ be $k$ bit random strings, and let $z_1,z_2$ be $k+1$ bit random strings.

We have that $A$ distinguishes the distribution of strings $D_0 : G(x_1)G(x_2)$ and 
$D_2: z_1z_2$.

Consider now the hybrid distribution of strings given by $D_1: G(x_1)z_2$.

By the triangle inequality $A$ also distinguishes between either $D_0$ and $D_1$ or between $D_1$ and $D_2$.

Assume without loss of generality that  $A$ distinguishes between $D_0$ and $D_1$.
Then we can break $G$ as follows. On input $y$, pick uniformly random $k$ bit string $x_1$ and give the string $G(x_1)y$ to $A$.