Vertically align a tikzpicture and forest

To top-align the trees, you need to set an appropriate (north) baseline for both trees. You have already done that for the tikzpicture tree. For the forest tree, you achieve this by adding options baseline and anchor=north to the root node (either in the root node specification, or in the preamble).

You need to specify anchor=north as baseline sets the node's anchor as the baseline for the picture (manual section 3.7.5).

The full code:

\documentclass{article}

\usepackage{tikz}
\usepackage{forest}

\usetikzlibrary{positioning}
\usetikzlibrary{automata}

\begin{document}

\begin{tikzpicture}[%
    node distance=0.8cm,
    ->,
    font=\small,
    baseline=(current bounding box.north)
]
\node[state] (s1) {$s_1$};
\node[state] (s2) [above left=of s1] {$s_2$};
\node[state] (s3) [right=of s1] {$s_8$};
\node[state] (s4) [left=of s2] {$s_3$};
\node[state] (s5) [left=of s1] {$s_5$};
\node[state] (s6) [right=of s2] {$s_9$};
\node[state] (s7) [below left=of s3] {$s_{11}$};
\node[state] (s8) [left=of s5] {$s_4$};
\node[state] (s9) [right=of s6] {$s_{10}$};
\node[state] (s10) [left=of s7] {$s_6$};
\node[state] (s11) [left=of s10] {$s_7$};

\path (s1) edge (s2);
\path (s1) edge (s3);
\path (s2) edge (s4);
\path (s2) edge (s5);
\path (s3) edge (s6);
\path (s3) edge (s7);
\path (s4) edge (s8);
\path (s6) edge (s9);
\path (s5) edge (s10);
\path (s5) edge (s11);
\end{tikzpicture}
\qquad
\begin{forest}
  baseline,anchor=north,
for tree={%
    math content,
    state,
    edge={->},
    l sep=0.1cm,
    s sep=0.1cm,
    font=\small
}
[s_1
    [s_2
        [s_3
            [s_4]
            [,phantom]
        ]
        [s_5
            [s_6]
            [s_7]
        ]
    ]
    [s_8
        [s_9
            [,phantom]
            [s_{10}]
        ]
        [s_{11}]
    ]
]
\end{forest}

\end{document}

To get the trees of the same height, first measure the height of the tikzpicture tree (https://tex.stackexchange.com/a/137367/16819) and then use this information to compute (within forest) the needed level separation.

This is the code, explanation below. Note that the node distance in the left tree needed to be increased, otherwise that tree was just not high enough.

\documentclass{article}

\usepackage{fullpage}
\usepackage{tikz}
\usepackage{forest}

\usetikzlibrary{positioning}
\usetikzlibrary{automata}
\usetikzlibrary{backgrounds}

\newlength{\mywidth}
\newlength{\myheight}

% computes width and height of tikzpicture
\makeatletter
\newcommand{\pgfsize}[2]{ % #1 = width, #2 = height
 \pgfextractx{\@tempdima}{\pgfpointdiff{\pgfpointanchor{current bounding box}{south west}}
 {\pgfpointanchor{current bounding box}{north east}}}
 \global#1=\@tempdima
 \pgfextracty{\@tempdima}{\pgfpointdiff{\pgfpointanchor{current bounding box}{south west}}
 {\pgfpointanchor{current bounding box}{north east}}}
 \global#2=\@tempdima
 %\draw (current bounding box.north east) -- (current bounding box.south west);
}
\makeatother



\begin{document}

\begin{center}
\begin{tikzpicture}[%
    node distance=1.5cm,
    ->,
    font=\small,
    %framed
]
\node[state] (s1) {$s_1$};
\node[state] (s2) [above left=of s1] {$s_2$};
\node[state] (s3) [right=of s1] {$s_8$};
\node[state] (s4) [left=of s2] {$s_3$};
\node[state] (s5) [left=of s1] {$s_5$};
\node[state] (s6) [right=of s2] {$s_9$};
\node[state] (s7) [below left=of s3] {$s_{11}$};
\node[state] (s8) [left=of s5] {$s_4$};
\node[state] (s9) [right=of s6] {$s_{10}$};
\node[state] (s10) [left=of s7] {$s_6$};
\node[state] (s11) [left=of s10] {$s_7$};

\path (s1) edge (s2);
\path (s1) edge (s3);
\path (s2) edge (s4);
\path (s2) edge (s5);
\path (s3) edge (s6);
\path (s3) edge (s7);
\path (s4) edge (s8);
\path (s6) edge (s9);
\path (s5) edge (s10);
\path (s5) edge (s11);
\pgfsize{\mywidth}{\myheight}
\end{tikzpicture}
\hfill
\begin{forest}
for tree={%
    math content,
    state,
    edge={->},
    font=\small,
},
before packing={%
  tempcounta/.max={level}{tree}, % count the levels in the tree
  tempdima=max_y()-min_y(), % node height (assuming it's the same for all nodes)
  tempdimb=((\myheight-(tempcounta()+1)*tempdima())/tempcounta()),
  if tempdimb<={0pt}{TeX={\errmessage{The left picture is not high enough!}}}{},
  for tree={l=0,l sep=tempdimb},
}
[s_1
    [s_2
        [s_3
            [s_4]
            [,phantom]
        ]
        [s_5
            [s_6]
            [s_7]
        ]
    ]
    [s_8
        [s_9
            [,phantom]
            [s_{10}]
        ]
        [s_{11}]
    ]
]
\end{forest}
\end{center}

\end{document}

So:

• The desired height is stored in \myheight.

• Aggregate function max (manual section 3.14) gets the deepest level.

• Using min_x, max_x, min_y, max_y, one can obtain the dimensions of a node. Note that this must be used after the typesetting nodes stage (see manual section 3.4.1). And as the desired level distance must be set before packing, the relevant code goes into temporal propagator before packing.

• Some simple math to compute the desired distance between the parent and child node

• The result is stored into l sep (not l!). This must be so because we have computed the distance between the southmost point of the parent and the northmost point of the child. (Setting l would set the distance between the parent's and the child's node anchors.) l must be set to 0pt to get rid of the default minimum and let the l sep determine the distance on its own.

An alternative way to set the baseline of the tree is to use tikz's baseline directly. This can be achieved by modifying (appending to) macro stored by begin draw (manual section 3.4.3). To set the baseline to the center of the entire tree, write

begin draw/.append code={[baseline=(current bounding box.center)]},

Note that for historic reasons, begin draw is not a forest toks register, but must be set using pgfkeys handler from the .code family, see PGF manual section 82.4.3. :-(