\medskip
\begin{tikzpicture}
  \tikzstyle{positive}=[pattern=north east lines, pattern color=blue!30]
  \tikzstyle{negative}=[pattern=dots, pattern color=red!30]

    % Language A
  \begin{scope}
    \draw[positive] (0,0) arc (0:180:1cm and 2cm) node[xshift=1cm, yshift=1cm] {$A$};
    \draw[negative] (0,0) arc (0:-180:1cm and 2cm) node [xshift=1cm, yshift=-.8cm] {$\bar{A}$};
    \draw (-2.2,0) -- (.2,0);
  \end{scope}

    % Language B
  \begin{scope}[xshift=3cm]
    \draw (0,0) ellipse (1cm and 2cm);
    \draw (-1.2,-.4) -- (1.2,.5);
    \node at (.3,1.5) {$B$};
    \node at (.3,-1.5) {$\bar{B}$};
    \node[ellipse, draw, positive] (fa) at (-0.1, .8) {\scriptsize $f(A)$};
    \node[ellipse, draw, negative] (fbara) at (-0.1, -.8) {\scriptsize $f(\bar{A})$};
  \end{scope}
    % Lines
  \draw[dashed] (-1, 2) -- (fa.north);
  \draw[dashed] (0, 0) -- (fa.south);
  \draw[dashed] (-1, -2) -- (fbara.south);
  \draw[dashed] (0, 0) -- (fbara.north);
  \draw[thick, ->] (.2, 2.5) -- node[below, midway] {$f$} (1.8, 2.5);

  \begin{scope}[xshift=4.5cm]
    \draw (0,2) -- (0,-2);
  \end{scope}

  \begin{scope}[xshift=4.7cm]
    \draw (1,-1) rectangle (5.5, 1);
    \node[anchor=north west] at (1,1) {Algorithm for $A$};
    \node[anchor=south east] at (5.5, -1) {\textit{also called} the ``reduction''};
    \node[draw, rectangle, anchor=west] (fbox) at (1.3,0) {$f$};
    \node[draw, rectangle, anchor=west] (bbox) at (2.3,0) {Algorithm for $B$};
    \draw[->, thick] (.5, 0) -- (fbox) -- (bbox) -- (6, 0);
    \node[anchor=south] at (.5,0) {\texttt{input}};
    \node[anchor=north] at (.5,0) {$x$};
  \end{scope}
\end{tikzpicture}
\medskip