Let's suppose that a language $L \in \operatorname{NSPACE}(f(n))$ where $f(n) = \Omega(\log(n))$. And now let's suppose that i have a probabilistic turing machine. Can this machine run in $O(f(n))$ space and answer yes for a $x \in L$ with Pr(yes)>1/2 and for a x that doesn't belong,answer no with Pr(no)=1? Le's suppose i dont care about time

Yes, if you do not care about running time, then you can simulate nondeterminism by a randomized algorithm with only a linear increase in space. Assume that $f(n)\ge\log n$ is spaceconstructible, and let $L\in\mathrm{NSPACE}(f)$. By definition, there exists a nondeterministic Turing machine $M_0$ working in space $f(n)$ which accepts $L$. By the Immerman–Szelepcsényi theorem, there exists a nondeterministic Turing machine $M_1$ working in space $O(f(n))$ which accepts the complement of $L$. Since $f$ is spaceconstructible, we can endow both TM with a clock counting to $2^{O(f(n))}$ (an upper bound on the number of configurations of $M_i$) to ensure that both machines terminate on every input and for any nondeterministic choices. Let $M$ be the following randomized algorithm. First, simulate $M_0$ by taking randomized choices instead of nondeterminism. If it accepts, then $M$ accepts. Otherwise, simulate $M_1$; if it accepts, then $M$ rejects. Otherwise, repeat the whole procedure. Clearly, $M$ works in space $O(f(n))$, and when it halts, it always gives the correct answer. Moreover, with probability $1$, $M$ has to eventually halt, since either $M_0$ or $M_1$ has a positive probability of accepting. Thus, $M$ is a zeroerror probabilistic algorithm for $L$. (The expected running time of $M$ may be as bad as exponential in the number of configurations of $M_i$, hence doubly exponential in $f(n)$.) Note that there are conflicting definitions of randomized space classes in the literature. Some authors use RL to denote onesided randomized logarithmic space without further restrictions, which by the argument above coincides with NL. Others require in addition the algorithm to run in polynomial time, and then it gives a presumably weaker class situated between L and NL. 


Exactly. And I also demand the problem to require NSPACE(s(n)) s(n) = Ω(logn) in the nondetermintistic machine and O(s(n)) in the probabilistic 

